/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / ast_comp / concurre.tar / concurrency / algecon.tex

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 5c 64 6f 63 75 6d 65 6e | 74 73 74 79 6c 65 7b 61 |\documen|tstyle{a|
|00000010| 72 74 69 63 6c 65 7d 0a | 0a 25 3d 3d 3d 3d 3d 3d |rticle}.|.%======|
|00000020| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00000030| 3d 3d 3d 3d 3d 3d 3d 3d | 0a 25 56 65 72 79 20 73 |========|.%Very s|
|00000040| 69 6d 70 6c 65 6d 69 6e | 64 65 64 20 6d 61 63 72 |implemin|ded macr|
|00000050| 6f 73 20 66 6f 72 20 64 | 72 61 77 69 6e 67 20 6c |os for d|rawing l|
|00000060| 61 74 74 69 63 65 73 2e | 20 20 45 61 73 69 6c 79 |attices.|  Easily|
|00000070| 20 62 65 6c 6c 65 64 20 | 26 20 77 68 69 73 74 6c | belled |& whistl|
|00000080| 65 64 0a 5c 61 72 72 61 | 79 63 6f 6c 73 65 70 3d |ed.\arra|ycolsep=|
|00000090| 30 70 74 0a 5c 64 65 66 | 5c 70 69 63 23 31 23 32 |0pt.\def|\pic#1#2|
|000000a0| 23 33 7b 5c 78 3d 23 31 | 5c 79 3d 23 32 20 5c 79 |#3{\x=#1|\y=#2 \y|
|000000b0| 79 3d 5c 79 20 5c 64 69 | 76 69 64 65 5c 79 79 20 |y=\y \di|vide\yy |
|000000c0| 62 79 32 0a 25 63 6f 6d | 70 75 74 65 20 5c 79 72 |by2.%com|pute \yr|
|000000d0| 20 3d 20 35 20 2a 20 28 | 5c 79 20 6d 6f 64 20 31 | = 5 * (|\y mod 1|
|000000e0| 29 0a 5c 79 72 3d 5c 79 | 5c 61 64 76 61 6e 63 65 |).\yr=\y|\advance|
|000000f0| 5c 79 72 20 62 79 2d 5c | 79 79 5c 61 64 76 61 6e |\yr by-\|yy\advan|
|00000100| 63 65 5c 79 72 20 62 79 | 2d 5c 79 79 5c 6d 75 6c |ce\yr by|-\yy\mul|
|00000110| 74 69 70 6c 79 5c 79 72 | 20 62 79 35 0a 5c 61 64 |tiply\yr| by5.\ad|
|00000120| 76 61 6e 63 65 5c 78 20 | 62 79 31 5c 61 64 76 61 |vance\x |by1\adva|
|00000130| 6e 63 65 5c 79 20 62 79 | 31 0a 5c 62 65 67 69 6e |nce\y by|1.\begin|
|00000140| 7b 61 72 72 61 79 7d 7b | 63 7d 0a 5c 62 65 67 69 |{array}{|c}.\begi|
|00000150| 6e 7b 70 69 63 74 75 72 | 65 7d 28 5c 74 68 65 5c |n{pictur|e}(\the\|
|00000160| 78 2c 5c 74 68 65 5c 79 | 29 28 2d 30 2e 35 2c 2d |x,\the\y|)(-0.5,-|
|00000170| 30 2e 35 29 23 33 5c 65 | 6e 64 7b 70 69 63 74 75 |0.5)#3\e|nd{pictu|
|00000180| 72 65 7d 0a 5c 65 6e 64 | 7b 61 72 72 61 79 7d 7d |re}.\end|{array}}|
|00000190| 0a 5c 64 65 66 5c 73 70 | 7b 5c 68 73 70 61 63 65 |.\def\sp|{\hspace|
|000001a0| 7b 2e 34 69 6e 7d 7d 0a | 5c 64 65 66 5c 68 64 23 |{.4in}}.|\def\hd#|
|000001b0| 31 7b 5c 62 65 67 69 6e | 7b 74 61 62 75 6c 61 72 |1{\begin|{tabular|
|000001c0| 7d 7b 63 7d 23 31 5c 65 | 6e 64 7b 74 61 62 75 6c |}{c}#1\e|nd{tabul|
|000001d0| 61 72 7d 7d 0a 5c 64 65 | 66 5c 70 23 31 23 32 7b |ar}}.\de|f\p#1#2{|
|000001e0| 5c 78 3d 23 31 5c 79 3d | 23 32 5c 70 75 74 28 23 |\x=#1\y=|#2\put(#|
|000001f0| 31 2c 23 32 29 7b 5c 6d | 61 6b 65 62 6f 78 28 30 |1,#2){\m|akebox(0|
|00000200| 2c 30 29 7b 24 5c 62 75 | 6c 6c 65 74 24 7d 7d 7d |,0){$\bu|llet$}}}|
|00000210| 0a 5c 64 65 66 5c 62 7b | 5c 70 75 74 28 5c 74 68 |.\def\b{|\put(\th|
|00000220| 65 5c 78 2c 5c 74 68 65 | 5c 79 29 7b 5c 6c 69 6e |e\x,\the|\y){\lin|
|00000230| 65 28 2d 31 2c 2d 31 29 | 7b 31 7d 7d 7d 0a 5c 64 |e(-1,-1)|{1}}}.\d|
|00000240| 65 66 5c 64 7b 5c 70 75 | 74 28 5c 74 68 65 5c 78 |ef\d{\pu|t(\the\x|
|00000250| 2c 5c 74 68 65 5c 79 29 | 7b 5c 6c 69 6e 65 28 20 |,\the\y)|{\line( |
|00000260| 30 2c 2d 31 29 7b 31 7d | 7d 7d 0a 5c 64 65 66 5c |0,-1){1}|}}.\def\|
|00000270| 66 7b 5c 70 75 74 28 5c | 74 68 65 5c 78 2c 5c 74 |f{\put(\|the\x,\t|
|00000280| 68 65 5c 79 29 7b 5c 6c | 69 6e 65 28 20 31 2c 2d |he\y){\l|ine( 1,-|
|00000290| 31 29 7b 31 7d 7d 7d 0a | 5c 64 65 66 5c 48 7b 5c |1){1}}}.|\def\H{\|
|000002a0| 6d 75 6c 74 69 70 75 74 | 28 5c 74 68 65 5c 78 2c |multiput|(\the\x,|
|000002b0| 5c 74 68 65 5c 79 29 28 | 20 2e 32 2c 20 20 30 29 |\the\y)(| .2,  0)|
|000002c0| 7b 35 7d 7b 5c 6d 61 6b | 65 62 6f 78 28 30 2c 30 |{5}{\mak|ebox(0,0|
|000002d0| 29 7b 5c 6c 61 72 67 65 | 2e 7d 7d 7d 0a 5c 64 65 |){\large|.}}}.\de|
|000002e0| 66 5c 48 48 7b 5c 6d 75 | 6c 74 69 70 75 74 28 5c |f\HH{\mu|ltiput(\|
|000002f0| 74 68 65 5c 78 2c 5c 74 | 68 65 5c 79 29 28 2e 32 |the\x,\t|he\y)(.2|
|00000300| 2c 20 20 30 29 7b 31 30 | 7d 7b 5c 6d 61 6b 65 62 |,  0){10|}{\makeb|
|00000310| 6f 78 28 30 2c 30 29 7b | 5c 6c 61 72 67 65 2e 7d |ox(0,0){|\large.}|
|00000320| 7d 7d 0a 5c 64 65 66 5c | 42 7b 5c 6d 75 6c 74 69 |}}.\def\|B{\multi|
|00000330| 70 75 74 28 5c 74 68 65 | 5c 78 2c 5c 74 68 65 5c |put(\the|\x,\the\|
|00000340| 79 29 28 2d 2e 32 2c 2d | 2e 32 29 7b 35 7d 7b 5c |y)(-.2,-|.2){5}{\|
|00000350| 6d 61 6b 65 62 6f 78 28 | 30 2c 30 29 7b 5c 6c 61 |makebox(|0,0){\la|
|00000360| 72 67 65 2e 7d 7d 7d 0a | 5c 64 65 66 5c 46 7b 5c |rge.}}}.|\def\F{\|
|00000370| 6d 75 6c 74 69 70 75 74 | 28 5c 74 68 65 5c 78 2c |multiput|(\the\x,|
|00000380| 5c 74 68 65 5c 79 29 28 | 20 2e 32 2c 2d 2e 32 29 |\the\y)(| .2,-.2)|
|00000390| 7b 35 7d 7b 5c 6d 61 6b | 65 62 6f 78 28 30 2c 30 |{5}{\mak|ebox(0,0|
|000003a0| 29 7b 5c 6c 61 72 67 65 | 2e 7d 7d 7d 0a 5c 6e 65 |){\large|.}}}.\ne|
|000003b0| 77 63 6f 75 6e 74 5c 78 | 20 5c 6e 65 77 63 6f 75 |wcount\x| \newcou|
|000003c0| 6e 74 5c 79 20 5c 6e 65 | 77 63 6f 75 6e 74 5c 78 |nt\y \ne|wcount\x|
|000003d0| 78 20 5c 6e 65 77 63 6f | 75 6e 74 5c 79 79 20 5c |x \newco|unt\yy \|
|000003e0| 6e 65 77 63 6f 75 6e 74 | 5c 78 72 20 5c 6e 65 77 |newcount|\xr \new|
|000003f0| 63 6f 75 6e 74 5c 79 72 | 0a 25 45 6e 64 20 6f 66 |count\yr|.%End of|
|00000400| 20 73 69 6d 70 6c 65 6d | 69 6e 64 65 64 20 6c 61 | simplem|inded la|
|00000410| 74 74 69 63 65 73 0a 25 | 3d 3d 3d 3d 3d 3d 3d 3d |ttices.%|========|
|00000420| 3d 3d 3d 3d 3d 3d 3d 3d | 3d 3d 3d 3d 3d 3d 3d 3d |========|========|
|00000430| 3d 3d 3d 3d 3d 3d 0a 0a | 5c 64 65 66 5c 3c 23 31 |======..|\def\<#1|
|00000440| 3e 7b 5c 6c 61 6e 67 6c | 65 20 23 31 20 5c 72 61 |>{\langl|e #1 \ra|
|00000450| 6e 67 6c 65 7d 0a 5c 64 | 65 66 5c 62 61 6e 67 7b |ngle}.\d|ef\bang{|
|00000460| 7b 5c 72 6d 20 21 7d 7d | 0a 5c 64 65 66 5c 71 75 |{\rm !}}|.\def\qu|
|00000470| 65 72 79 7b 7b 5c 72 6d | 20 3f 7d 7d 0a 5c 64 65 |ery{{\rm| ?}}.\de|
|00000480| 66 5c 74 77 6f 7b 7b 5c | 62 66 20 32 7d 7d 0a 5c |f\two{{\|bf 2}}.\|
|00000490| 64 65 66 5c 6f 69 6d 70 | 7b 5c 6d 61 74 68 72 65 |def\oimp|{\mathre|
|000004a0| 6c 7b 5c 72 65 6c 62 61 | 72 5c 6d 6b 65 72 6e 2d |l{\relba|r\mkern-|
|000004b0| 37 2e 35 6d 75 5c 63 69 | 72 63 7d 7d 0a 5c 64 65 |7.5mu\ci|rc}}.\de|
|000004c0| 66 5c 72 73 7b 5c 6d 61 | 74 68 62 69 6e 7b 5c 68 |f\rs{\ma|thbin{\h|
|000004d0| 62 6f 78 7b 2b 7b 5c 6b | 65 72 6e 2d 2e 37 35 34 |box{+{\k|ern-.754|
|000004e0| 65 6d 5c 6c 6f 77 65 72 | 20 31 2e 36 65 78 5c 68 |em\lower| 1.6ex\h|
|000004f0| 62 6f 78 7b 5c 63 68 61 | 72 27 32 35 7d 7d 5c 6b |box{\cha|r'25}}\k|
|00000500| 65 72 6e 2e 32 35 65 6d | 7d 7d 7d 0a 5c 64 65 66 |ern.25em|}}}.\def|
|00000510| 5c 6f 6e 7b 5e 5c 62 6f | 74 7d 20 5c 64 65 66 5c |\on{^\bo|t} \def\|
|00000520| 63 6f 6e 7b 5c 62 72 65 | 76 65 7b 7e 7d 7d 20 5c |con{\bre|ve{~}} \|
|00000530| 64 65 66 5c 63 6f 6d 7b | 5e 2d 7d 0a 5c 64 65 66 |def\com{|^-}.\def|
|00000540| 5c 6f 70 7b 7b 5c 6d 62 | 6f 78 7b 24 5e 7b 5c 72 |\op{{\mb|ox{$^{\r|
|00000550| 6d 20 6f 70 7d 24 7d 7d | 7d 0a 5c 64 65 66 5c 53 |m op}$}}|}.\def\S|
|00000560| 65 74 7b 7b 5c 62 66 20 | 53 65 74 7d 7d 0a 5c 64 |et{{\bf |Set}}.\d|
|00000570| 65 66 5c 50 6f 73 7b 7b | 5c 62 66 20 50 6f 73 7d |ef\Pos{{|\bf Pos}|
|00000580| 7d 0a 5c 64 65 66 5c 45 | 76 7b 7b 5c 62 66 20 45 |}.\def\E|v{{\bf E|
|00000590| 76 7d 7d 0a 5c 64 65 66 | 5c 53 74 7b 7b 5c 62 66 |v}}.\def|\St{{\bf|
|000005a0| 20 53 74 7d 7d 0a 5c 64 | 65 66 5c 43 73 6c 7b 7b | St}}.\d|ef\Csl{{|
|000005b0| 5c 62 66 20 43 53 4c 61 | 74 7d 7d 0a 5c 64 65 66 |\bf CSLa|t}}.\def|
|000005c0| 5c 71 65 64 7b 5c 76 72 | 75 6c 65 20 68 65 69 67 |\qed{\vr|ule heig|
|000005d0| 68 74 36 70 74 20 77 69 | 64 74 68 34 70 74 20 64 |ht6pt wi|dth4pt d|
|000005e0| 65 70 74 68 30 70 74 7d | 20 25 20 65 6e 64 2d 6f |epth0pt}| % end-o|
|000005f0| 66 2d 70 72 6f 6f 66 20 | 65 74 63 2e 0a 5c 64 65 |f-proof |etc..\de|
|00000600| 66 5c 71 23 31 7b 5c 62 | 5c 6b 65 72 6e 31 70 74 |f\q#1{\b|\kern1pt|
|00000610| 24 5f 7b 23 31 7d 24 7d | 0a 5c 64 65 66 5c 74 23 |$_{#1}$}|.\def\t#|
|00000620| 31 7b 5c 6d 61 6b 65 62 | 6f 78 28 30 2c 31 29 7b |1{\makeb|ox(0,1){|
|00000630| 24 5f 7b 23 31 7d 24 7d | 7d 0a 5c 64 65 66 5c 73 |$_{#1}$}|}.\def\s|
|00000640| 23 31 7b 5c 6d 61 6b 65 | 62 6f 78 28 30 2c 31 29 |#1{\make|box(0,1)|
|00000650| 7b 24 23 31 24 7d 7d 0a | 0a 5c 62 65 67 69 6e 7b |{$#1$}}.|.\begin{|
|00000660| 64 6f 63 75 6d 65 6e 74 | 7d 0a 0a 0a 5c 74 69 74 |document|}...\tit|
|00000670| 6c 65 7b 41 72 69 74 68 | 6d 65 74 69 63 20 2b 20 |le{Arith|metic + |
|00000680| 4c 6f 67 69 63 20 2b 20 | 47 65 6f 6d 65 74 72 79 |Logic + |Geometry|
|00000690| 20 3d 20 43 6f 6e 63 75 | 72 72 65 6e 63 79 7d 0a | = Concu|rrency}.|
|000006a0| 0a 5c 61 75 74 68 6f 72 | 7b 56 61 75 67 68 61 6e |.\author|{Vaughan|
|000006b0| 20 50 72 61 74 74 5c 74 | 68 61 6e 6b 73 7b 54 68 | Pratt\t|hanks{Th|
|000006c0| 69 73 20 77 6f 72 6b 20 | 77 61 73 20 73 75 70 70 |is work |was supp|
|000006d0| 6f 72 74 65 64 20 62 79 | 0a 74 68 65 20 4e 61 74 |orted by|.the Nat|
|000006e0| 69 6f 6e 61 6c 20 53 63 | 69 65 6e 63 65 20 46 6f |ional Sc|ience Fo|
|000006f0| 75 6e 64 61 74 69 6f 6e | 20 75 6e 64 65 72 20 67 |undation| under g|
|00000700| 72 61 6e 74 20 6e 75 6d | 62 65 72 20 43 43 52 2d |rant num|ber CCR-|
|00000710| 38 38 31 34 39 32 31 2e | 7d 20 5c 5c 0a 53 74 61 |8814921.|} \\.Sta|
|00000720| 6e 66 6f 72 64 20 55 6e | 69 76 65 72 73 69 74 79 |nford Un|iversity|
|00000730| 7d 0a 0a 5c 6d 61 6b 65 | 74 69 74 6c 65 0a 0a 5c |}..\make|title..\|
|00000740| 73 65 74 63 6f 75 6e 74 | 65 72 7b 73 65 63 74 69 |setcount|er{secti|
|00000750| 6f 6e 7d 7b 2d 31 7d 0a | 0a 5c 73 65 63 74 69 6f |on}{-1}.|.\sectio|
|00000760| 6e 7b 49 6e 74 72 6f 64 | 75 63 74 69 6f 6e 7d 0a |n{Introd|uction}.|
|00000770| 0a 49 6e 20 64 65 66 69 | 6e 69 6e 67 20 63 6f 6e |.In defi|ning con|
|00000780| 63 75 72 72 65 6e 63 79 | 20 6f 6e 65 20 64 69 63 |currency| one dic|
|00000790| 68 6f 74 6f 6d 79 20 74 | 68 61 74 20 68 61 73 20 |hotomy t|hat has |
|000007a0| 61 72 69 73 65 6e 20 69 | 73 20 62 65 74 77 65 65 |arisen i|s betwee|
|000007b0| 6e 0a 72 65 64 75 63 74 | 69 6f 6e 69 73 6d 20 61 |n.reduct|ionism a|
|000007c0| 6e 64 20 70 72 69 6d 69 | 74 69 76 69 73 6d 2e 20 |nd primi|tivism. |
|000007d0| 20 54 68 65 20 72 65 64 | 75 63 74 69 6f 6e 69 73 | The red|uctionis|
|000007e0| 74 20 76 69 65 77 70 6f | 69 6e 74 20 72 65 64 75 |t viewpo|int redu|
|000007f0| 63 65 73 0a 63 6f 6e 63 | 75 72 72 65 6e 74 20 62 |ces.conc|urrent b|
|00000800| 65 68 61 76 69 6f 72 20 | 74 6f 20 6e 6f 6e 64 65 |ehavior |to nonde|
|00000810| 74 65 72 6d 69 6e 69 73 | 74 69 63 20 73 65 71 75 |terminis|tic sequ|
|00000820| 65 6e 74 69 61 6c 20 62 | 65 68 61 76 69 6f 72 20 |ential b|ehavior |
|00000830| 62 79 20 76 69 65 77 69 | 6e 67 0a 69 74 20 61 73 |by viewi|ng.it as|
|00000840| 20 69 6e 74 65 72 6c 65 | 61 76 69 6e 67 2e 20 20 | interle|aving.  |
|00000850| 54 68 65 20 70 72 69 6d | 69 74 69 76 65 20 73 63 |The prim|itive sc|
|00000860| 68 6f 6f 6c 20 74 72 65 | 61 74 73 20 63 6f 6e 63 |hool tre|ats conc|
|00000870| 75 72 72 65 6e 74 20 62 | 65 68 61 76 69 6f 72 20 |urrent b|ehavior |
|00000880| 61 73 0a 61 20 62 61 73 | 69 63 20 66 6f 72 6d 20 |as.a bas|ic form |
|00000890| 6f 66 20 62 65 68 61 76 | 69 6f 72 20 69 6e 20 69 |of behav|ior in i|
|000008a0| 74 73 20 6f 77 6e 20 72 | 69 67 68 74 2c 20 64 69 |ts own r|ight, di|
|000008b0| 73 74 69 6e 63 74 20 66 | 72 6f 6d 20 61 6e 64 20 |stinct f|rom and |
|000008c0| 69 6e 64 65 65 64 0a 6d | 6f 72 65 20 67 65 6e 65 |indeed.m|ore gene|
|000008d0| 72 61 6c 20 74 68 61 6e | 20 73 65 71 75 65 6e 74 |ral than| sequent|
|000008e0| 69 61 6c 20 62 65 68 61 | 76 69 6f 72 2e 0a 0a 41 |ial beha|vior...A|
|000008f0| 20 62 61 73 69 63 20 61 | 72 67 75 6d 65 6e 74 20 | basic a|rgument |
|00000900| 66 6f 72 20 72 65 64 75 | 63 74 69 6f 6e 69 73 6d |for redu|ctionism|
|00000910| 20 69 73 20 74 68 61 74 | 20 6e 6f 6e 73 65 71 75 | is that| nonsequ|
|00000920| 65 6e 74 69 61 6c 20 62 | 65 68 61 76 69 6f 72 20 |ential b|ehavior |
|00000930| 69 73 0a 62 65 73 74 20 | 75 6e 64 65 72 73 74 6f |is.best |understo|
|00000940| 6f 64 20 69 6e 20 74 65 | 72 6d 73 20 6f 66 20 73 |od in te|rms of s|
|00000950| 65 71 75 65 6e 74 69 61 | 6c 20 62 65 68 61 76 69 |equentia|l behavi|
|00000960| 6f 72 20 62 65 63 61 75 | 73 65 20 74 68 65 20 6c |or becau|se the l|
|00000970| 61 74 74 65 72 20 69 73 | 0a 74 68 65 20 6b 69 6e |atter is|.the kin|
|00000980| 64 20 77 65 20 75 6e 64 | 65 72 73 74 61 6e 64 20 |d we und|erstand |
|00000990| 6e 61 74 75 72 61 6c 6c | 79 20 61 6e 64 20 69 6e |naturall|y and in|
|000009a0| 73 74 69 6e 63 74 69 76 | 65 6c 79 2c 20 6f 72 20 |stinctiv|ely, or |
|000009b0| 61 74 20 6c 65 61 73 74 | 20 74 68 65 0a 6b 69 6e |at least| the.kin|
|000009c0| 64 20 77 69 74 68 20 77 | 68 69 63 68 20 77 65 20 |d with w|hich we |
|000009d0| 68 61 76 65 20 62 79 20 | 66 61 72 20 74 68 65 20 |have by |far the |
|000009e0| 6d 6f 73 74 20 65 78 70 | 65 72 69 65 6e 63 65 2e |most exp|erience.|
|000009f0| 20 20 41 74 20 74 68 65 | 20 63 6f 6e 73 63 69 6f |  At the| conscio|
|00000a00| 75 73 0a 6c 65 76 65 6c | 20 65 61 63 68 20 6f 66 |us.level| each of|
|00000a10| 20 75 73 20 61 70 70 65 | 61 72 73 20 74 6f 20 62 | us appe|ars to b|
|00000a20| 65 20 61 20 73 65 71 75 | 65 6e 74 69 61 6c 20 61 |e a sequ|ential a|
|00000a30| 67 65 6e 74 2e 20 20 4f | 75 72 20 6c 69 6d 62 73 |gent.  O|ur limbs|
|00000a40| 2c 20 6d 75 73 63 6c 65 | 73 2c 0a 61 6e 64 20 63 |, muscle|s,.and c|
|00000a50| 65 6c 6c 73 20 6d 61 79 | 20 61 63 74 20 63 6f 6e |ells may| act con|
|00000a60| 63 75 72 72 65 6e 74 6c | 79 2c 20 62 75 74 20 6f |currentl|y, but o|
|00000a70| 75 72 20 63 6f 6e 74 72 | 6f 6c 20 6f 66 20 74 68 |ur contr|ol of th|
|00000a80| 65 6d 20 69 73 20 62 61 | 73 69 63 61 6c 6c 79 0a |em is ba|sically.|
|00000a90| 73 65 71 75 65 6e 74 69 | 61 6c 20 61 6e 64 20 74 |sequenti|al and t|
|00000aa0| 68 65 20 6e 65 63 65 73 | 73 61 72 79 20 63 6f 6e |he neces|sary con|
|00000ab0| 63 75 72 72 65 6e 74 20 | 63 6f 6e 74 72 6f 6c 20 |current |control |
|00000ac0| 73 65 65 6d 73 20 74 6f | 20 68 61 70 70 65 6e 20 |seems to| happen |
|00000ad0| 62 65 6c 6f 77 0a 74 68 | 65 20 6c 65 76 65 6c 20 |below.th|e level |
|00000ae0| 6f 66 20 6f 75 72 20 63 | 6f 6e 73 63 69 6f 75 73 |of our c|onscious|
|00000af0| 20 63 6f 6e 74 72 6f 6c | 2c 20 6f 72 20 69 74 20 | control|, or it |
|00000b00| 77 6f 75 6c 64 20 62 65 | 20 6a 75 73 74 20 61 73 |would be| just as|
|00000b10| 20 65 61 73 79 20 74 6f | 0a 74 77 69 64 64 6c 65 | easy to|.twiddle|
|00000b20| 20 6f 75 72 20 74 68 75 | 6d 62 73 20 69 6e 20 6f | our thu|mbs in o|
|00000b30| 70 70 6f 73 69 74 65 20 | 64 69 72 65 63 74 69 6f |pposite |directio|
|00000b40| 6e 73 20 61 73 20 69 6e | 20 74 68 65 20 73 61 6d |ns as in| the sam|
|00000b50| 65 20 64 69 72 65 63 74 | 69 6f 6e 2e 0a 0a 50 72 |e direct|ion...Pr|
|00000b60| 69 6d 69 74 69 76 69 73 | 74 73 20 6f 62 6a 65 63 |imitivis|ts objec|
|00000b70| 74 20 74 68 61 74 20 72 | 65 64 75 63 69 6e 67 20 |t that r|educing |
|00000b80| 63 6f 6e 63 75 72 72 65 | 6e 74 20 62 65 68 61 76 |concurre|nt behav|
|00000b90| 69 6f 72 20 74 6f 20 73 | 65 71 75 65 6e 74 69 61 |ior to s|equentia|
|00000ba0| 6c 0a 6d 61 6b 65 73 20 | 74 68 65 20 66 6f 72 6d |l.makes |the form|
|00000bb0| 65 72 20 68 61 72 64 65 | 72 20 72 61 74 68 65 72 |er harde|r rather|
|00000bc0| 20 74 68 61 6e 20 65 61 | 73 69 65 72 20 74 6f 20 | than ea|sier to |
|00000bd0| 75 6e 64 65 72 73 74 61 | 6e 64 2e 20 20 42 79 20 |understa|nd.  By |
|00000be0| 61 6e 61 6c 6f 67 79 2c | 0a 6f 72 67 61 6e 69 7a |analogy,|.organiz|
|00000bf0| 69 6e 67 20 61 20 54 56 | 20 69 6d 61 67 65 20 61 |ing a TV| image a|
|00000c00| 73 20 74 68 65 20 73 65 | 71 75 65 6e 63 65 20 6f |s the se|quence o|
|00000c10| 66 20 69 74 73 20 73 63 | 61 6e 20 6c 69 6e 65 73 |f its sc|an lines|
|00000c20| 20 69 6e 20 6f 6e 65 0a | 64 69 6d 65 6e 73 69 6f | in one.|dimensio|
|00000c30| 6e 2c 20 74 68 65 20 66 | 6f 72 6d 20 69 6e 20 77 |n, the f|orm in w|
|00000c40| 68 69 63 68 20 69 74 20 | 61 72 72 69 76 65 73 20 |hich it |arrives |
|00000c50| 61 74 20 79 6f 75 72 20 | 72 65 63 65 69 76 65 72 |at your |receiver|
|00000c60| 2c 20 6d 61 6b 65 73 20 | 69 74 20 6d 75 63 68 0a |, makes |it much.|
|00000c70| 68 61 72 64 65 72 20 74 | 6f 20 73 65 65 2e 20 20 |harder t|o see.  |
|00000c80| 49 74 20 69 73 20 6e 6f | 74 20 73 6f 20 6d 75 63 |It is no|t so muc|
|00000c90| 68 20 61 20 71 75 65 73 | 74 69 6f 6e 20 6f 66 20 |h a ques|tion of |
|00000ca0| 77 68 65 74 68 65 72 20 | 69 6e 66 6f 72 6d 61 74 |whether |informat|
|00000cb0| 69 6f 6e 20 69 73 0a 6c | 6f 73 74 20 61 73 20 74 |ion is.l|ost as t|
|00000cc0| 68 65 20 63 6f 6d 70 6c | 65 78 69 74 79 20 6f 66 |he compl|exity of|
|00000cd0| 20 70 69 65 63 69 6e 67 | 20 74 68 65 20 69 6e 66 | piecing| the inf|
|00000ce0| 6f 72 6d 61 74 69 6f 6e | 20 62 61 63 6b 20 74 6f |ormation| back to|
|00000cf0| 67 65 74 68 65 72 2e 20 | 20 45 76 65 6e 0a 69 66 |gether. | Even.if|
|00000d00| 20 72 65 64 75 63 74 69 | 6f 6e 69 73 6d 20 69 73 | reducti|onism is|
|00000d10| 20 74 68 65 20 6f 6e 6c | 79 20 6d 6f 64 65 20 6f | the onl|y mode o|
|00000d20| 66 20 74 68 6f 75 67 68 | 74 20 70 72 65 73 65 6e |f though|t presen|
|00000d30| 74 6c 79 20 61 76 61 69 | 6c 61 62 6c 65 20 66 6f |tly avai|lable fo|
|00000d40| 72 20 74 68 65 0a 70 65 | 72 63 65 70 74 69 6f 6e |r the.pe|rception|
|00000d50| 20 6f 66 20 63 6f 6e 63 | 75 72 72 65 6e 74 20 62 | of conc|urrent b|
|00000d60| 65 68 61 76 69 6f 72 2c | 20 69 74 20 69 73 20 73 |ehavior,| it is s|
|00000d70| 75 63 68 20 61 20 70 6f | 6f 72 20 77 61 79 20 6f |uch a po|or way o|
|00000d80| 66 20 74 68 69 6e 6b 69 | 6e 67 0a 61 62 6f 75 74 |f thinki|ng.about|
|00000d90| 20 69 74 20 74 68 61 74 | 20 77 65 20 61 72 65 20 | it that| we are |
|00000da0| 62 65 74 74 65 72 20 6f | 66 66 20 6c 65 61 72 6e |better o|ff learn|
|00000db0| 69 6e 67 20 74 6f 20 64 | 65 61 6c 20 77 69 74 68 |ing to d|eal with|
|00000dc0| 20 63 6f 6e 63 75 72 72 | 65 6e 63 79 20 69 6e 0a | concurr|ency in.|
|00000dd0| 69 74 73 20 6f 77 6e 20 | 72 69 67 68 74 20 74 68 |its own |right th|
|00000de0| 61 6e 20 70 65 72 73 69 | 73 74 69 6e 67 20 77 69 |an persi|sting wi|
|00000df0| 74 68 20 72 65 64 75 63 | 74 69 6f 6e 69 73 6d 2e |th reduc|tionism.|
|00000e00| 0a 0a 52 65 64 75 63 74 | 69 6f 6e 69 73 74 73 20 |..Reduct|ionists |
|00000e10| 63 6f 75 6e 74 65 72 20 | 74 68 61 74 20 70 72 69 |counter |that pri|
|00000e20| 6d 69 74 69 76 69 73 6d | 20 69 73 20 6e 6f 74 20 |mitivism| is not |
|00000e30| 66 75 6c 6c 79 20 61 62 | 73 74 72 61 63 74 2c 20 |fully ab|stract, |
|00000e40| 74 68 61 74 20 69 73 2c | 0a 64 72 61 77 73 20 75 |that is,|.draws u|
|00000e50| 6e 6f 62 73 65 72 76 61 | 62 6c 65 20 64 69 73 74 |nobserva|ble dist|
|00000e60| 69 6e 63 74 69 6f 6e 73 | 2e 20 20 49 6e 20 74 68 |inctions|.  In th|
|00000e70| 65 20 63 6f 6e 74 65 78 | 74 20 6f 66 20 64 61 74 |e contex|t of dat|
|00000e80| 61 66 6c 6f 77 20 6e 65 | 74 73 20 4b 6f 6b 0a 5c |aflow ne|ts Kok.\|
|00000e90| 63 69 74 65 7b 4b 6f 6b | 38 37 7d 2c 20 4a 6f 6e |cite{Kok|87}, Jon|
|00000ea0| 73 73 6f 6e 20 5c 63 69 | 74 65 7b 4a 6f 6e 38 39 |sson \ci|te{Jon89|
|00000eb0| 7d 2c 20 52 61 62 69 6e | 6f 76 69 63 68 20 61 6e |}, Rabin|ovich an|
|00000ec0| 64 20 54 72 61 6b 68 74 | 65 6e 62 72 6f 74 0a 5c |d Trakht|enbrot.\|
|00000ed0| 63 69 74 65 7b 52 54 38 | 38 61 7d 2c 20 52 75 73 |cite{RT8|8a}, Rus|
|00000ee0| 73 65 6c 6c 20 5c 63 69 | 74 65 7b 52 75 73 38 39 |sell \ci|te{Rus89|
|00000ef0| 7d 2c 20 61 6e 64 20 6f | 74 68 65 72 73 20 68 61 |}, and o|thers ha|
|00000f00| 76 65 20 73 68 6f 77 6e | 20 74 68 61 74 0a 72 65 |ve shown| that.re|
|00000f10| 64 75 63 74 69 6f 6e 69 | 73 6d 2c 20 75 6e 6c 69 |ductioni|sm, unli|
|00000f20| 6b 65 20 70 72 69 6d 69 | 74 69 76 69 73 6d 2c 20 |ke primi|tivism, |
|00000f30| 69 73 20 66 75 6c 6c 79 | 20 61 62 73 74 72 61 63 |is fully| abstrac|
|00000f40| 74 2e 0a 0a 54 68 65 20 | 70 72 69 6d 69 74 69 76 |t...The |primitiv|
|00000f50| 69 73 74 20 61 6e 73 77 | 65 72 20 69 73 20 74 68 |ist answ|er is th|
|00000f60| 61 74 20 74 68 65 73 65 | 20 72 65 73 75 6c 74 73 |at these| results|
|00000f70| 20 70 72 65 73 75 6d 65 | 20 74 68 65 20 6f 62 73 | presume| the obs|
|00000f80| 65 72 76 65 72 20 74 6f | 20 62 65 0a 73 65 71 75 |erver to| be.sequ|
|00000f90| 65 6e 74 69 61 6c 2c 20 | 61 6e 64 20 74 68 61 74 |ential, |and that|
|00000fa0| 20 74 68 65 20 72 65 64 | 75 63 74 69 6f 6e 69 73 | the red|uctionis|
|00000fb0| 74 73 20 68 61 76 65 20 | 73 68 6f 77 6e 20 6f 6e |ts have |shown on|
|00000fc0| 6c 79 20 74 68 61 74 20 | 7b 5c 69 74 20 61 0a 73 |ly that |{\it a.s|
|00000fd0| 65 71 75 65 6e 74 69 61 | 6c 20 6f 62 73 65 72 76 |equentia|l observ|
|00000fe0| 65 72 20 70 65 72 63 65 | 69 76 65 73 20 61 20 73 |er perce|ives a s|
|00000ff0| 65 71 75 65 6e 74 69 61 | 6c 20 77 6f 72 6c 64 2e |equentia|l world.|
|00001000| 7d 20 20 50 6c 6f 74 6b | 69 6e 20 61 6e 64 20 50 |}  Plotk|in and P|
|00001010| 72 61 74 74 0a 5c 63 69 | 74 65 7b 50 50 7d 20 68 |ratt.\ci|te{PP} h|
|00001020| 61 76 65 20 73 68 6f 77 | 6e 20 74 68 61 74 20 61 |ave show|n that a|
|00001030| 20 74 65 61 6d 20 6f 66 | 20 24 6e 24 20 73 65 71 | team of| $n$ seq|
|00001040| 75 65 6e 74 69 61 6c 20 | 6f 62 73 65 72 76 65 72 |uential |observer|
|00001050| 73 20 63 61 6e 0a 72 65 | 73 6f 6c 76 65 20 64 69 |s can.re|solve di|
|00001060| 73 74 69 6e 63 74 69 6f | 6e 73 20 69 6e 76 69 73 |stinctio|ns invis|
|00001070| 69 62 6c 65 20 74 6f 20 | 24 6e 2d 31 24 20 6f 62 |ible to |$n-1$ ob|
|00001080| 73 65 72 76 65 72 73 2c | 20 77 68 65 6e 63 65 20 |servers,| whence |
|00001090| 66 6f 72 20 6d 6f 72 65 | 20 74 68 61 6e 0a 6f 6e |for more| than.on|
|000010a0| 65 20 6f 62 73 65 72 76 | 65 72 20 7b 5c 69 74 20 |e observ|er {\it |
|000010b0| 72 65 64 75 63 74 69 6f | 6e 69 73 6d 20 69 73 20 |reductio|nism is |
|000010c0| 75 6e 73 6f 75 6e 64 7d | 20 28 61 73 73 65 72 74 |unsound}| (assert|
|000010d0| 73 20 6f 62 73 65 72 76 | 61 62 6c 79 20 66 61 6c |s observ|ably fal|
|000010e0| 73 65 0a 65 71 75 61 6c | 69 74 69 65 73 29 2e 0a |se.equal|ities)..|
|000010f0| 0a 52 65 64 75 63 74 69 | 6f 6e 69 73 6d 20 68 61 |.Reducti|onism ha|
|00001100| 73 20 65 6d 65 72 67 65 | 64 20 69 6e 20 72 65 73 |s emerge|d in res|
|00001110| 70 6f 6e 73 65 20 70 72 | 69 6d 61 72 69 6c 79 20 |ponse pr|imarily |
|00001120| 74 6f 20 74 68 65 20 6e | 65 65 64 73 20 6f 66 20 |to the n|eeds of |
|00001130| 73 6f 66 74 77 61 72 65 | 0a 65 6e 67 69 6e 65 65 |software|.enginee|
|00001140| 72 73 2c 20 6d 61 6b 69 | 6e 67 20 61 20 6e 75 6d |rs, maki|ng a num|
|00001150| 62 65 72 20 6f 66 20 61 | 73 73 75 6d 70 74 69 6f |ber of a|ssumptio|
|00001160| 6e 73 20 76 61 6c 69 64 | 20 69 6e 20 74 68 61 74 |ns valid| in that|
|00001170| 20 64 6f 6d 61 69 6e 20 | 62 75 74 20 6e 6f 74 0a | domain |but not.|
|00001180| 69 6e 20 6d 61 6e 79 20 | 6f 74 68 65 72 20 73 65 |in many |other se|
|00001190| 74 74 69 6e 67 73 20 77 | 68 65 72 65 20 63 6f 6e |ttings w|here con|
|000011a0| 63 75 72 72 65 6e 63 79 | 20 74 68 65 6f 72 79 20 |currency| theory |
|000011b0| 63 6f 75 6c 64 20 62 65 | 20 66 72 75 69 74 66 75 |could be| fruitfu|
|000011c0| 6c 6c 79 0a 61 70 70 6c | 69 65 64 2e 20 20 54 68 |lly.appl|ied.  Th|
|000011d0| 75 73 2c 20 77 69 74 68 | 20 74 68 65 20 69 6e 74 |us, with| the int|
|000011e0| 65 72 6c 65 61 76 69 6e | 67 20 6f 66 20 6d 61 63 |erleavin|g of mac|
|000011f0| 68 69 6e 65 20 69 6e 73 | 74 72 75 63 74 69 6f 6e |hine ins|truction|
|00001200| 73 20 69 6e 20 6d 69 6e | 64 2c 0a 69 74 20 70 72 |s in min|d,.it pr|
|00001210| 65 73 75 6d 65 73 20 66 | 69 78 65 64 20 61 74 6f |esumes f|ixed ato|
|00001220| 6d 69 63 69 74 79 20 6f | 66 20 65 76 65 6e 74 73 |micity o|f events|
|00001230| 20 69 6e 20 6f 72 64 65 | 72 20 74 6f 20 64 65 66 | in orde|r to def|
|00001240| 69 6e 65 0a 69 6e 74 65 | 72 6c 65 61 76 69 6e 67 |ine.inte|rleaving|
|00001250| 2d 2d 2d 6f 6e 63 65 20 | 61 6e 20 65 76 65 6e 74 |---once |an event|
|00001260| 20 68 61 73 20 62 65 65 | 6e 20 64 65 63 6c 61 72 | has bee|n declar|
|00001270| 65 64 20 61 74 6f 6d 69 | 63 20 74 68 65 72 65 20 |ed atomi|c there |
|00001280| 63 61 6e 20 62 65 20 6e | 6f 0a 73 75 62 73 65 71 |can be n|o.subseq|
|00001290| 75 65 6e 74 20 60 60 6f | 70 65 6e 69 6e 67 20 75 |uent ``o|pening u|
|000012a0| 70 27 27 20 6f 66 20 74 | 68 65 20 65 76 65 6e 74 |p'' of t|he event|
|000012b0| 20 74 6f 20 72 65 76 65 | 61 6c 20 73 75 62 65 76 | to reve|al subev|
|000012c0| 65 6e 74 73 20 74 68 61 | 74 20 6d 69 67 68 74 0a |ents tha|t might.|
|000012d0| 62 65 20 69 6e 74 65 72 | 6c 65 61 76 65 64 20 77 |be inter|leaved w|
|000012e0| 69 74 68 20 74 68 65 20 | 73 75 62 65 76 65 6e 74 |ith the |subevent|
|000012f0| 73 20 6f 66 20 73 6f 6d | 65 20 6f 74 68 65 72 20 |s of som|e other |
|00001300| 70 72 65 76 69 6f 75 73 | 6c 79 20 61 74 6f 6d 69 |previous|ly atomi|
|00001310| 63 0a 65 76 65 6e 74 2e | 20 20 46 75 72 74 68 65 |c.event.|  Furthe|
|00001320| 72 6d 6f 72 65 20 72 65 | 64 75 63 74 69 6f 6e 69 |rmore re|ductioni|
|00001330| 73 6d 20 69 73 20 74 69 | 6d 69 6e 67 20 69 6e 64 |sm is ti|ming ind|
|00001340| 65 70 65 6e 64 65 6e 74 | 3a 20 6e 6f 20 6c 69 6d |ependent|: no lim|
|00001350| 69 74 73 20 61 72 65 0a | 70 6c 61 63 65 64 20 6f |its are.|placed o|
|00001360| 6e 20 74 68 65 20 72 65 | 6c 61 74 69 76 65 20 73 |n the re|lative s|
|00001370| 70 65 65 64 73 20 6f 66 | 20 70 61 72 61 6c 6c 65 |peeds of| paralle|
|00001380| 6c 20 70 72 6f 63 65 73 | 73 6f 72 73 2e 20 20 41 |l proces|sors.  A|
|00001390| 6e 64 20 72 65 64 75 63 | 74 69 6f 6e 69 73 6d 0a |nd reduc|tionism.|
|000013a0| 61 73 73 75 6d 65 73 20 | 64 69 73 63 72 65 74 65 |assumes |discrete|
|000013b0| 6e 65 73 73 2c 20 72 75 | 6c 69 6e 67 20 6f 75 74 |ness, ru|ling out|
|000013c0| 20 63 6f 6e 74 69 6e 75 | 6f 75 73 20 70 72 6f 63 | continu|ous proc|
|000013d0| 65 73 73 65 73 2e 0a 0a | 54 68 69 73 20 70 61 70 |esses...|This pap|
|000013e0| 65 72 20 74 69 65 73 20 | 74 6f 67 65 74 68 65 72 |er ties |together|
|000013f0| 20 74 68 72 65 65 20 70 | 72 69 6d 69 74 69 76 69 | three p|rimitivi|
|00001400| 73 74 20 76 69 65 77 73 | 20 6f 66 20 63 6f 6e 63 |st views| of conc|
|00001410| 75 72 72 65 6e 63 79 20 | 77 68 6f 73 65 0a 64 65 |urrency |whose.de|
|00001420| 76 65 6c 6f 70 6d 65 6e | 74 20 74 68 65 20 61 75 |velopmen|t the au|
|00001430| 74 68 6f 72 20 68 61 73 | 20 68 61 64 20 73 6f 6d |thor has| had som|
|00001440| 65 20 69 6e 76 6f 6c 76 | 65 6d 65 6e 74 20 77 69 |e involv|ement wi|
|00001450| 74 68 2c 20 6e 61 6d 65 | 6c 79 20 74 68 65 0a 61 |th, name|ly the.a|
|00001460| 72 69 74 68 6d 65 74 69 | 63 20 6f 66 20 73 63 68 |rithmeti|c of sch|
|00001470| 65 64 75 6c 65 73 2c 20 | 74 68 65 20 6c 6f 67 69 |edules, |the logi|
|00001480| 63 20 6f 66 20 73 63 68 | 65 64 75 6c 65 2d 61 75 |c of sch|edule-au|
|00001490| 74 6f 6d 61 74 6f 6e 20 | 64 75 61 6c 69 74 79 2c |tomaton |duality,|
|000014a0| 20 61 6e 64 0a 74 68 65 | 20 67 65 6f 6d 65 74 72 | and.the| geometr|
|000014b0| 79 20 6f 66 20 61 75 74 | 6f 6d 61 74 61 2e 20 20 |y of aut|omata.  |
|000014c0| 53 65 70 61 72 61 74 65 | 6c 79 20 65 61 63 68 20 |Separate|ly each |
|000014d0| 6f 66 20 74 68 65 73 65 | 20 76 69 65 77 73 20 73 |of these| views s|
|000014e0| 68 65 64 0a 63 6f 6e 73 | 69 64 65 72 61 62 6c 65 |hed.cons|iderable|
|000014f0| 20 6c 69 67 68 74 20 6f | 6e 20 63 6f 6e 63 75 72 | light o|n concur|
|00001500| 72 65 6e 63 79 2e 20 20 | 4f 75 72 20 67 6f 61 6c |rency.  |Our goal|
|00001510| 20 68 65 72 65 20 69 73 | 20 74 6f 20 62 72 69 6e | here is| to brin|
|00001520| 67 20 74 68 65 73 65 0a | 74 68 72 65 65 20 76 69 |g these.|three vi|
|00001530| 65 77 73 20 74 6f 67 65 | 74 68 65 72 20 63 6f 68 |ews toge|ther coh|
|00001540| 65 72 65 6e 74 6c 79 20 | 69 6e 20 74 68 65 20 6f |erently |in the o|
|00001550| 6e 65 20 70 6c 61 63 65 | 2e 20 20 54 68 65 20 67 |ne place|.  The g|
|00001560| 65 6e 65 72 61 6c 20 70 | 69 63 74 75 72 65 0a 69 |eneral p|icture.i|
|00001570| 73 20 61 73 20 66 6f 6c | 6c 6f 77 73 2e 0a 24 24 |s as fol|lows..$$|
|00001580| 5c 62 65 67 69 6e 7b 61 | 72 72 61 79 7d 7b 63 63 |\begin{a|rray}{cc|
|00001590| 63 7d 31 26 32 26 33 5c | 63 72 5c 66 62 6f 78 7b |c}1&2&3\|cr\fbox{|
|000015a0| 5c 68 64 7b 41 72 69 74 | 68 6d 65 74 69 63 5c 5c |\hd{Arit|hmetic\\|
|000015b0| 6f 66 5c 5c 53 63 68 65 | 64 75 6c 65 73 7d 7d 26 |of\\Sche|dules}}&|
|000015c0| 0a 5c 6c 6f 6e 67 6c 65 | 66 74 61 72 72 6f 77 5c |.\longle|ftarrow\|
|000015d0| 68 64 7b 4c 6f 67 69 63 | 20 6f 66 5c 5c 20 53 63 |hd{Logic| of\\ Sc|
|000015e0| 68 65 64 75 6c 65 2d 41 | 75 74 6f 6d 61 74 6f 6e |hedule-A|utomaton|
|000015f0| 5c 5c 44 75 61 6c 69 74 | 79 7d 5c 6c 6f 6e 67 72 |\\Dualit|y}\longr|
|00001600| 69 67 68 74 61 72 72 6f | 77 26 0a 5c 66 62 6f 78 |ightarro|w&.\fbox|
|00001610| 7b 5c 68 64 7b 47 65 6f | 6d 65 74 72 79 5c 5c 6f |{\hd{Geo|metry\\o|
|00001620| 66 5c 5c 41 75 74 6f 6d | 61 74 61 7d 7d 5c 65 6e |f\\Autom|ata}}\en|
|00001630| 64 7b 61 72 72 61 79 7d | 24 24 0a 42 79 20 61 20 |d{array}|$$.By a |
|00001640| 6e 69 63 65 20 63 6f 69 | 6e 63 69 64 65 6e 63 65 |nice coi|ncidence|
|00001650| 20 74 68 65 20 6e 75 6d | 62 65 72 69 6e 67 20 69 | the num|bering i|
|00001660| 73 20 62 6f 74 68 20 73 | 65 63 74 69 6f 6e 20 6e |s both s|ection n|
|00001670| 75 6d 62 65 72 20 61 6e | 64 20 24 55 46 28 31 29 |umber an|d $UF(1)|
|00001680| 24 0a 28 63 61 72 64 69 | 6e 61 6c 69 74 79 20 6f |$.(cardi|nality o|
|00001690| 66 20 74 68 65 20 73 69 | 6e 67 6c 79 20 67 65 6e |f the si|ngly gen|
|000016a0| 65 72 61 74 65 64 20 66 | 72 65 65 20 61 6c 67 65 |erated f|ree alge|
|000016b0| 62 72 61 29 20 69 6e 20 | 74 68 65 20 72 65 73 70 |bra) in |the resp|
|000016c0| 65 63 74 69 76 65 0a 65 | 71 75 61 74 69 6f 6e 61 |ective.e|quationa|
|000016d0| 6c 20 63 61 74 65 67 6f | 72 69 65 73 2e 20 20 54 |l catego|ries.  T|
|000016e0| 68 61 74 20 69 73 2c 20 | 31 20 69 73 20 74 68 65 |hat is, |1 is the|
|000016f0| 20 62 61 73 69 63 20 63 | 6f 75 6e 74 69 6e 67 20 | basic c|ounting |
|00001700| 65 6c 65 6d 65 6e 74 20 | 6f 66 0a 61 72 69 74 68 |element |of.arith|
|00001710| 6d 65 74 69 63 2c 20 32 | 20 28 74 72 75 65 20 61 |metic, 2| (true a|
|00001720| 6e 64 20 66 61 6c 73 65 | 29 20 69 73 20 28 74 68 |nd false|) is (th|
|00001730| 65 20 64 75 61 6c 20 6f | 66 29 20 74 68 65 20 62 |e dual o|f) the b|
|00001740| 61 73 69 63 20 64 75 61 | 6c 69 7a 69 6e 67 0a 65 |asic dua|lizing.e|
|00001750| 6c 65 6d 65 6e 74 20 6f | 66 20 6c 6f 67 69 63 2c |lement o|f logic,|
|00001760| 20 61 6e 64 20 33 20 28 | 62 65 67 69 6e 6e 69 6e | and 3 (|beginnin|
|00001770| 67 2c 20 6d 69 64 64 6c | 65 2c 20 61 6e 64 20 65 |g, middl|e, and e|
|00001780| 6e 64 29 20 69 73 20 74 | 68 65 20 62 61 73 69 63 |nd) is t|he basic|
|00001790| 0a 73 70 61 63 65 2d 66 | 69 6c 6c 69 6e 67 20 65 |.space-f|illing e|
|000017a0| 6c 65 6d 65 6e 74 20 6f | 66 20 67 65 6f 6d 65 74 |lement o|f geomet|
|000017b0| 72 79 2e 0a 0a 41 20 7b | 5c 69 74 20 73 63 68 65 |ry...A {|\it sche|
|000017c0| 64 75 6c 65 7d 20 69 73 | 20 61 20 73 65 74 20 6f |dule} is| a set o|
|000017d0| 66 20 6e 65 63 65 73 73 | 61 72 79 20 65 76 65 6e |f necess|ary even|
|000017e0| 74 73 20 6f 66 20 74 72 | 61 6e 73 69 74 69 6f 6e |ts of tr|ansition|
|000017f0| 20 63 6f 6e 73 74 72 61 | 69 6e 65 64 0a 62 79 20 | constra|ined.by |
|00001800| 66 61 63 74 73 20 61 62 | 6f 75 74 20 70 61 69 72 |facts ab|out pair|
|00001810| 73 20 6f 66 20 65 76 65 | 6e 74 73 2e 20 20 41 6e |s of eve|nts.  An|
|00001820| 20 7b 5c 69 74 20 61 75 | 74 6f 6d 61 74 6f 6e 7d | {\it au|tomaton}|
|00001830| 20 69 73 20 61 20 73 65 | 74 20 6f 66 0a 70 6f 73 | is a se|t of.pos|
|00001840| 73 69 62 6c 65 20 73 74 | 61 74 65 73 20 6f 66 20 |sible st|ates of |
|00001850| 69 6e 66 6f 72 6d 61 74 | 69 6f 6e 20 65 6e 61 62 |informat|ion enab|
|00001860| 6c 65 64 20 62 79 20 74 | 72 61 6e 73 69 74 69 6f |led by t|ransitio|
|00001870| 6e 73 20 62 65 74 77 65 | 65 6e 20 70 61 69 72 73 |ns betwe|en pairs|
|00001880| 20 6f 66 0a 73 74 61 74 | 65 73 2e 0a 0a 54 68 69 | of.stat|es...Thi|
|00001890| 73 20 77 6f 72 64 69 6e | 67 20 65 6d 70 68 61 73 |s wordin|g emphas|
|000018a0| 69 7a 65 73 20 74 68 65 | 20 64 75 61 6c 69 74 79 |izes the| duality|
|000018b0| 20 6f 66 20 65 76 65 6e | 74 20 61 6e 64 20 73 74 | of even|t and st|
|000018c0| 61 74 65 2e 20 20 45 76 | 65 6e 74 73 20 61 72 65 |ate.  Ev|ents are|
|000018d0| 0a 6e 65 63 65 73 73 61 | 72 79 20 69 6e 20 74 68 |.necessa|ry in th|
|000018e0| 61 74 20 61 6e 20 75 6e | 63 6f 6e 73 74 72 61 69 |at an un|constrai|
|000018f0| 6e 65 64 20 73 63 68 65 | 64 75 6c 65 20 28 6e 6f |ned sche|dule (no|
|00001900| 20 72 65 6c 61 74 69 6f | 6e 73 20 62 65 74 77 65 | relatio|ns betwe|
|00001910| 65 6e 0a 65 76 65 6e 74 | 73 29 20 72 65 71 75 69 |en.event|s) requi|
|00001920| 72 65 73 20 74 68 61 74 | 20 61 6c 6c 20 65 76 65 |res that| all eve|
|00001930| 6e 74 73 20 62 65 20 70 | 65 72 66 6f 72 6d 65 64 |nts be p|erformed|
|00001940| 2e 20 20 53 74 61 74 65 | 73 20 61 72 65 20 70 6f |.  State|s are po|
|00001950| 73 73 69 62 6c 65 0a 28 | 74 68 65 20 70 6f 73 73 |ssible.(|the poss|
|00001960| 69 62 6c 65 20 77 6f 72 | 6c 64 73 20 6f 66 20 4b |ible wor|lds of K|
|00001970| 72 69 70 6b 65 20 73 65 | 6d 61 6e 74 69 63 73 29 |ripke se|mantics)|
|00001980| 20 69 6e 20 74 68 61 74 | 20 61 20 64 69 73 61 62 | in that| a disab|
|00001990| 6c 65 64 20 61 75 74 6f | 6d 61 74 6f 6e 0a 28 6e |led auto|maton.(n|
|000019a0| 6f 20 74 72 61 6e 73 69 | 74 69 6f 6e 73 20 62 65 |o transi|tions be|
|000019b0| 74 77 65 65 6e 20 73 74 | 61 74 65 73 29 20 70 65 |tween st|ates) pe|
|000019c0| 72 6d 69 74 73 20 6f 6e | 65 20 73 74 61 74 65 20 |rmits on|e state |
|000019d0| 74 6f 20 62 65 20 6f 63 | 63 75 70 69 65 64 2e 0a |to be oc|cupied..|
|000019e0| 0a 48 65 72 65 20 77 65 | 20 6c 69 6d 69 74 20 74 |.Here we| limit t|
|000019f0| 68 65 20 72 65 6c 61 74 | 69 6f 6e 73 20 62 65 74 |he relat|ions bet|
|00001a00| 77 65 65 6e 20 65 76 65 | 6e 74 73 20 74 6f 20 74 |ween eve|nts to t|
|00001a10| 68 6f 73 65 20 6f 66 20 | 74 65 6d 70 6f 72 61 6c |hose of |temporal|
|00001a20| 20 6f 72 64 65 72 0a 28 | 60 60 62 69 6e 61 72 79 | order.(|``binary|
|00001a30| 20 64 69 73 74 61 6e 63 | 65 27 27 29 20 61 6e 64 | distanc|e'') and|
|00001a40| 20 63 6f 6e 66 6c 69 63 | 74 2e 20 20 49 6e 20 74 | conflic|t.  In t|
|00001a50| 68 65 20 61 62 73 65 6e | 63 65 20 6f 66 20 63 6f |he absen|ce of co|
|00001a60| 6e 66 6c 69 63 74 20 74 | 68 69 73 0a 61 72 69 74 |nflict t|his.arit|
|00001a70| 68 6d 65 74 69 63 20 68 | 61 73 20 66 6f 72 20 69 |hmetic h|as for i|
|00001a80| 74 73 20 70 72 6f 67 65 | 6e 69 74 6f 72 20 74 68 |ts proge|nitor th|
|00001a90| 65 20 42 69 72 6b 68 6f | 66 66 20 61 72 69 74 68 |e Birkho|ff arith|
|00001aa0| 6d 65 74 69 63 20 6f 66 | 20 70 61 72 74 69 61 6c |metic of| partial|
|00001ab0| 0a 6f 72 64 65 72 73 20 | 5c 63 69 74 65 7b 42 69 |.orders |\cite{Bi|
|00001ac0| 72 6b 34 32 7d 20 61 73 | 20 61 20 62 61 73 69 63 |rk42} as| a basic|
|00001ad0| 20 70 72 6f 67 72 61 6d | 6d 69 6e 67 20 6c 61 6e | program|ming lan|
|00001ae0| 67 75 61 67 65 20 66 6f | 72 20 73 63 68 65 64 75 |guage fo|r schedu|
|00001af0| 6c 65 73 2e 0a 0a 54 68 | 65 20 42 69 72 6b 68 6f |les...Th|e Birkho|
|00001b00| 66 66 2d 53 74 6f 6e 65 | 20 64 75 61 6c 69 74 79 |ff-Stone| duality|
|00001b10| 20 5c 63 69 74 65 7b 42 | 69 72 33 33 2c 53 74 6f | \cite{B|ir33,Sto|
|00001b20| 33 37 7d 20 6f 66 20 70 | 6f 73 65 74 73 20 61 73 |37} of p|osets as|
|00001b30| 0a 64 65 74 65 72 6d 69 | 6e 69 73 74 69 63 20 73 |.determi|nistic s|
|00001b40| 63 68 65 64 75 6c 65 73 | 20 61 6e 64 20 64 69 73 |chedules| and dis|
|00001b50| 74 72 69 62 75 74 69 76 | 65 20 6c 61 74 74 69 63 |tributiv|e lattic|
|00001b60| 65 73 20 61 73 20 64 65 | 74 65 72 6d 69 6e 69 73 |es as de|terminis|
|00001b70| 74 69 63 0a 61 75 74 6f | 6d 61 74 61 20 74 68 65 |tic.auto|mata the|
|00001b80| 6e 20 63 6f 6e 73 74 69 | 74 75 74 65 73 20 61 20 |n consti|tutes a |
|00001b90| 6c 6f 67 69 63 20 69 6e | 20 77 68 69 63 68 20 74 |logic in| which t|
|00001ba0| 68 65 20 64 75 61 6c 69 | 74 79 20 6f 66 20 74 72 |he duali|ty of tr|
|00001bb0| 75 65 20 61 6e 64 0a 66 | 61 6c 73 65 20 61 72 65 |ue and.f|alse are|
|00001bc0| 20 72 65 70 6c 61 63 65 | 64 20 62 79 20 74 68 65 | replace|d by the|
|00001bd0| 20 64 75 61 6c 69 74 79 | 20 6f 66 20 64 6f 69 6e | duality| of doin|
|00001be0| 67 20 61 6e 64 20 62 65 | 69 6e 67 2e 20 20 54 68 |g and be|ing.  Th|
|00001bf0| 69 73 20 64 75 61 6c 69 | 74 79 0a 69 6e 74 65 72 |is duali|ty.inter|
|00001c00| 63 68 61 6e 67 65 73 20 | 65 76 65 6e 74 73 20 28 |changes |events (|
|00001c10| 61 73 20 61 63 74 69 6f | 6e 73 29 20 61 6e 64 20 |as actio|ns) and |
|00001c20| 73 74 61 74 65 73 20 28 | 61 73 20 66 61 63 74 73 |states (|as facts|
|00001c30| 20 6f 72 20 6d 6f 64 65 | 6c 73 29 2c 20 61 6e 64 | or mode|ls), and|
|00001c40| 0a 64 75 61 6c 69 7a 65 | 73 20 74 68 65 20 61 72 |.dualize|s the ar|
|00001c50| 69 74 68 6d 65 74 69 63 | 20 62 79 20 69 6e 74 65 |ithmetic| by inte|
|00001c60| 72 63 68 61 6e 67 69 6e | 67 20 73 75 6d 20 61 6e |rchangin|g sum an|
|00001c70| 64 20 70 72 6f 64 75 63 | 74 2e 0a 44 65 74 65 72 |d produc|t..Deter|
|00001c80| 6d 69 6e 69 73 74 69 63 | 20 73 63 68 65 64 75 6c |ministic| schedul|
|00001c90| 65 73 20 65 78 74 65 6e | 64 20 74 6f 20 65 76 65 |es exten|d to eve|
|00001ca0| 6e 74 20 73 74 72 75 63 | 74 75 72 65 73 20 76 69 |nt struc|tures vi|
|00001cb0| 61 20 61 20 6e 6f 74 69 | 6f 6e 20 6f 66 0a 65 76 |a a noti|on of.ev|
|00001cc0| 65 6e 74 20 63 6f 6e 66 | 6c 69 63 74 2c 20 69 6e |ent conf|lict, in|
|00001cd0| 74 72 6f 64 75 63 69 6e | 67 20 61 6e 20 65 6c 65 |troducin|g an ele|
|00001ce0| 6d 65 6e 74 20 6f 66 20 | 63 68 6f 69 63 65 20 6f |ment of |choice o|
|00001cf0| 72 20 6e 6f 6e 64 65 74 | 65 72 6d 69 6e 69 73 6d |r nondet|erminism|
|00001d00| 2e 0a 44 75 61 6c 6c 79 | 2c 20 64 65 74 65 72 6d |..Dually|, determ|
|00001d10| 69 6e 69 73 74 69 63 20 | 61 75 74 6f 6d 61 74 61 |inistic |automata|
|00001d20| 20 65 78 74 65 6e 64 20 | 74 6f 20 62 72 61 6e 63 | extend |to branc|
|00001d30| 68 69 6e 67 20 61 75 74 | 6f 6d 61 74 61 2e 0a 0a |hing aut|omata...|
|00001d40| 54 68 65 20 73 74 75 64 | 79 20 6f 66 20 6f 72 64 |The stud|y of ord|
|00001d50| 65 72 65 64 20 73 65 74 | 73 20 66 69 78 65 73 20 |ered set|s fixes |
|00001d60| 61 20 76 65 72 74 69 63 | 61 6c 20 6f 72 69 65 6e |a vertic|al orien|
|00001d70| 74 61 74 69 6f 6e 20 61 | 6e 64 0a 63 6f 6e 76 65 |tation a|nd.conve|
|00001d80| 6e 74 69 6f 6e 61 6c 6c | 79 20 6c 6f 63 61 74 65 |ntionall|y locate|
|00001d90| 73 20 74 72 75 74 68 20 | 61 74 20 74 68 65 20 74 |s truth |at the t|
|00001da0| 6f 70 20 61 6e 64 20 66 | 61 6c 73 65 68 6f 6f 64 |op and f|alsehood|
|00001db0| 20 61 74 20 74 68 65 20 | 62 6f 74 74 6f 6d 2e 0a | at the |bottom..|
|00001dc0| 46 6f 72 20 42 69 72 6b | 68 6f 66 66 2d 53 74 6f |For Birk|hoff-Sto|
|00001dd0| 6e 65 20 64 75 61 6c 69 | 74 79 20 77 65 20 73 68 |ne duali|ty we sh|
|00001de0| 61 6c 6c 20 61 6e 61 6c | 6f 67 6f 75 73 6c 79 20 |all anal|ogously |
|00001df0| 66 69 78 20 61 20 68 6f | 72 69 7a 6f 6e 74 61 6c |fix a ho|rizontal|
|00001e00| 0a 6f 72 69 65 6e 74 61 | 74 69 6f 6e 20 61 6e 64 |.orienta|tion and|
|00001e10| 20 63 6f 6e 76 65 6e 74 | 69 6f 6e 61 6c 6c 79 20 | convent|ionally |
|00001e20| 6c 6f 63 61 74 65 20 73 | 63 68 65 64 75 6c 65 73 |locate s|chedules|
|00001e30| 20 6f 6e 20 74 68 65 20 | 6c 65 66 74 20 61 6e 64 | on the |left and|
|00001e40| 0a 61 75 74 6f 6d 61 74 | 61 20 6f 6e 20 74 68 65 |.automat|a on the|
|00001e50| 20 72 69 67 68 74 2e 0a | 0a 54 68 65 72 65 20 69 | right..|.There i|
|00001e60| 73 20 73 6f 6d 65 20 70 | 72 65 63 65 64 65 6e 74 |s some p|recedent|
|00001e70| 20 66 6f 72 20 63 61 6c | 6c 69 6e 67 20 74 68 65 | for cal|ling the|
|00001e80| 73 65 20 74 68 65 20 67 | 65 6f 6d 65 74 72 69 63 |se the g|eometric|
|00001e90| 20 61 6e 64 20 61 6c 67 | 65 62 72 61 69 63 0a 73 | and alg|ebraic.s|
|00001ea0| 69 64 65 73 20 72 65 73 | 70 65 63 74 69 76 65 6c |ides res|pectivel|
|00001eb0| 79 2c 20 6d 6f 74 69 76 | 61 74 65 64 20 62 79 20 |y, motiv|ated by |
|00001ec0| 74 68 65 20 63 61 73 65 | 20 6f 66 20 53 74 6f 6e |the case| of Ston|
|00001ed0| 65 20 64 75 61 6c 69 74 | 79 2e 20 20 48 6f 77 65 |e dualit|y.  Howe|
|00001ee0| 76 65 72 0a 74 68 65 20 | 6d 65 65 74 2d 6a 6f 69 |ver.the |meet-joi|
|00001ef0| 6e 20 6d 6f 62 69 6c 69 | 74 79 20 61 6e 64 20 74 |n mobili|ty and t|
|00001f00| 68 65 20 67 65 6f 6d 65 | 74 72 69 63 20 69 6e 74 |he geome|tric int|
|00001f10| 65 72 70 72 65 74 61 74 | 69 6f 6e 20 6f 66 20 64 |erpretat|ion of d|
|00001f20| 69 73 74 72 69 62 75 74 | 69 76 65 0a 6c 61 74 74 |istribut|ive.latt|
|00001f30| 69 63 65 73 20 74 68 61 | 74 20 77 65 20 64 65 73 |ices tha|t we des|
|00001f40| 63 72 69 62 65 20 62 65 | 6c 6f 77 20 73 68 6f 77 |cribe be|low show|
|00001f50| 20 74 68 61 74 20 74 68 | 65 73 65 20 64 69 73 74 | that th|ese dist|
|00001f60| 69 6e 63 74 69 6f 6e 73 | 20 61 72 65 20 6e 6f 74 |inctions| are not|
|00001f70| 0a 61 6c 6c 20 74 68 61 | 74 20 77 65 6c 6c 20 63 |.all tha|t well c|
|00001f80| 6f 72 72 65 6c 61 74 65 | 64 20 77 69 74 68 20 53 |orrelate|d with S|
|00001f90| 74 6f 6e 65 20 64 75 61 | 6c 69 74 79 2c 20 69 6e |tone dua|lity, in|
|00001fa0| 20 74 68 61 74 20 77 65 | 20 63 61 6e 20 66 69 6e | that we| can fin|
|00001fb0| 64 20 62 6f 74 68 0a 67 | 65 6f 6d 65 74 72 69 63 |d both.g|eometric|
|00001fc0| 20 61 6e 64 20 61 6c 67 | 65 62 72 61 69 63 20 65 | and alg|ebraic e|
|00001fd0| 6c 65 6d 65 6e 74 73 20 | 6f 6e 20 62 6f 74 68 20 |lements |on both |
|00001fe0| 73 69 64 65 73 20 73 69 | 6d 75 6c 74 61 6e 65 6f |sides si|multaneo|
|00001ff0| 75 73 6c 79 2e 0a 0a 54 | 68 69 73 20 63 6f 6e 66 |usly...T|his conf|
|00002000| 75 73 69 6f 6e 20 64 6f | 65 73 20 6e 6f 74 20 61 |usion do|es not a|
|00002010| 72 69 73 65 20 66 6f 72 | 20 6e 65 63 65 73 73 69 |rise for| necessi|
|00002020| 74 79 20 61 6e 64 20 70 | 6f 73 73 69 62 69 6c 69 |ty and p|ossibili|
|00002030| 74 79 2e 20 20 57 68 65 | 6e 20 77 65 0a 70 75 74 |ty.  Whe|n we.put|
|00002040| 20 74 68 65 20 73 65 74 | 73 20 77 69 74 68 20 74 | the set|s with t|
|00002050| 68 65 20 6e 65 63 65 73 | 73 61 72 79 20 65 6c 65 |he neces|sary ele|
|00002060| 6d 65 6e 74 73 20 6f 6e | 20 6f 6e 65 20 73 69 64 |ments on| one sid|
|00002070| 65 2c 20 74 68 6f 73 65 | 20 77 69 74 68 20 74 68 |e, those| with th|
|00002080| 65 0a 70 6f 73 73 69 62 | 6c 65 20 65 6c 65 6d 65 |e.possib|le eleme|
|00002090| 6e 74 73 20 61 75 74 6f | 6d 61 74 69 63 61 6c 6c |nts auto|maticall|
|000020a0| 79 20 62 65 6c 6f 6e 67 | 20 74 6f 20 74 68 65 20 |y belong| to the |
|000020b0| 6f 74 68 65 72 20 73 69 | 64 65 2e 20 20 54 68 65 |other si|de.  The|
|000020c0| 20 63 6f 6e 63 72 65 74 | 65 0a 69 6e 74 65 72 70 | concret|e.interp|
|000020d0| 72 65 74 61 74 69 6f 6e | 20 6f 66 20 74 68 65 73 |retation| of thes|
|000020e0| 65 20 73 65 74 73 20 61 | 73 20 72 65 73 70 65 63 |e sets a|s respec|
|000020f0| 74 69 76 65 6c 79 20 73 | 63 68 65 64 75 6c 65 73 |tively s|chedules|
|00002100| 20 61 6e 64 20 61 75 74 | 6f 6d 61 74 61 0a 70 61 | and aut|omata.pa|
|00002110| 72 61 6c 6c 65 6c 73 20 | 74 68 65 20 63 6f 6e 63 |rallels |the conc|
|00002120| 72 65 74 65 20 69 6e 74 | 65 72 70 72 65 74 61 74 |rete int|erpretat|
|00002130| 69 6f 6e 20 6f 66 20 74 | 68 65 20 6f 72 64 65 72 |ion of t|he order|
|00002140| 2d 74 68 65 6f 72 65 74 | 69 63 20 6e 6f 74 69 6f |-theoret|ic notio|
|00002150| 6e 73 20 6f 66 0a 30 20 | 6f 72 20 62 6f 74 74 6f |ns of.0 |or botto|
|00002160| 6d 20 61 6e 64 20 31 20 | 6f 72 20 74 6f 70 20 61 |m and 1 |or top a|
|00002170| 73 20 74 68 65 20 6c 6f | 67 69 63 61 6c 20 6e 6f |s the lo|gical no|
|00002180| 74 69 6f 6e 73 20 6f 66 | 20 66 61 6c 73 65 20 61 |tions of| false a|
|00002190| 6e 64 20 74 72 75 65 0a | 72 65 73 70 65 63 74 69 |nd true.|respecti|
|000021a0| 76 65 6c 79 2e 0a 0a 41 | 6c 74 68 6f 75 67 68 20 |vely...A|lthough |
|000021b0| 77 65 20 68 61 76 65 20 | 6c 69 6d 69 74 65 64 20 |we have |limited |
|000021c0| 6f 75 72 73 65 6c 76 65 | 73 20 68 65 72 65 20 74 |ourselve|s here t|
|000021d0| 6f 20 74 69 6d 65 20 61 | 73 20 61 20 70 61 72 74 |o time a|s a part|
|000021e0| 69 61 6c 20 6f 72 64 65 | 72 2c 20 77 65 0a 68 61 |ial orde|r, we.ha|
|000021f0| 76 65 20 65 6c 73 65 77 | 68 65 72 65 20 73 74 75 |ve elsew|here stu|
|00002200| 64 69 65 64 20 61 20 6d | 6f 72 65 20 67 65 6e 65 |died a m|ore gene|
|00002210| 72 61 6c 20 66 6f 72 6d | 20 6f 66 20 74 65 6d 70 |ral form| of temp|
|00002220| 6f 72 61 6c 20 6f 72 67 | 61 6e 69 7a 61 74 69 6f |oral org|anizatio|
|00002230| 6e 2c 0a 74 68 65 20 67 | 65 6e 65 72 61 6c 69 7a |n,.the g|eneraliz|
|00002240| 65 64 20 6d 65 74 72 69 | 63 20 73 70 61 63 65 20 |ed metri|c space |
|00002250| 5c 63 69 74 65 7b 43 43 | 4d 50 7d 2e 20 20 54 68 |\cite{CC|MP}.  Th|
|00002260| 65 20 74 65 6d 70 6f 72 | 61 6c 20 6f 72 64 65 72 |e tempor|al order|
|00002270| 20 72 65 6c 61 74 69 6f | 6e 0a 24 78 5c 6c 65 20 | relatio|n.$x\le |
|00002280| 79 24 20 69 73 20 67 65 | 6e 65 72 61 6c 69 7a 65 |y$ is ge|neralize|
|00002290| 64 20 74 6f 20 61 20 64 | 69 73 74 61 6e 63 65 20 |d to a d|istance |
|000022a0| 6d 65 74 72 69 63 20 24 | 64 28 78 2c 79 29 24 2c |metric $|d(x,y)$,|
|000022b0| 20 6e 6f 74 20 6e 65 63 | 65 73 73 61 72 69 6c 79 | not nec|essarily|
|000022c0| 0a 73 79 6d 6d 65 74 72 | 69 63 2c 20 72 65 70 72 |.symmetr|ic, repr|
|000022d0| 65 73 65 6e 74 69 6e 67 | 20 61 20 64 65 6c 61 79 |esenting| a delay|
|000022e0| 20 61 6e 64 20 73 61 74 | 69 73 66 79 69 6e 67 20 | and sat|isfying |
|000022f0| 61 20 74 72 69 61 6e 67 | 6c 65 20 69 6e 65 71 75 |a triang|le inequ|
|00002300| 61 6c 69 74 79 0a 24 64 | 28 78 2c 79 29 5c 6f 74 |ality.$d|(x,y)\ot|
|00002310| 69 6d 65 73 20 64 28 79 | 2c 7a 29 5c 73 71 73 75 |imes d(y|,z)\sqsu|
|00002320| 62 73 65 74 65 71 20 64 | 28 78 2c 7a 29 24 20 28 |bseteq d|(x,z)$ (|
|00002330| 61 6e 64 20 69 74 73 20 | 7a 65 72 6f 61 72 79 20 |and its |zeroary |
|00002340| 66 6f 72 6d 0a 24 5c 74 | 6f 70 5c 73 71 73 75 62 |form.$\t|op\sqsub|
|00002350| 73 65 74 65 71 20 64 28 | 78 2c 78 29 24 20 77 68 |seteq d(|x,x)$ wh|
|00002360| 65 72 65 20 24 5c 6f 74 | 69 6d 65 73 24 20 28 77 |ere $\ot|imes$ (w|
|00002370| 69 74 68 20 75 6e 69 74 | 20 24 5c 74 6f 70 24 29 |ith unit| $\top$)|
|00002380| 0a 61 73 73 6f 63 69 61 | 74 69 76 65 6c 79 20 61 |.associa|tively a|
|00002390| 63 63 75 6d 75 6c 61 74 | 65 73 20 64 65 6c 61 79 |ccumulat|es delay|
|000023a0| 73 20 28 60 60 68 6f 72 | 69 7a 6f 6e 74 61 6c 6c |s (``hor|izontall|
|000023b0| 79 27 27 29 20 61 6e 64 | 20 24 5c 73 71 73 75 62 |y'') and| $\sqsub|
|000023c0| 73 65 74 65 71 24 0a 6f | 72 64 65 72 73 20 64 65 |seteq$.o|rders de|
|000023d0| 6c 61 79 73 20 62 79 20 | 6c 6f 67 69 63 61 6c 20 |lays by |logical |
|000023e0| 73 74 72 65 6e 67 74 68 | 20 28 60 60 76 65 72 74 |strength| (``vert|
|000023f0| 69 63 61 6c 6c 79 27 27 | 29 2e 20 20 54 68 69 73 |ically''|).  This|
|00002400| 20 6c 65 76 65 6c 20 6f | 66 0a 67 65 6e 65 72 61 | level o|f.genera|
|00002410| 6c 69 74 79 20 61 64 6d | 69 74 73 20 6e 6f 74 69 |lity adm|its noti|
|00002420| 6f 6e 73 20 73 75 63 68 | 20 61 73 20 63 61 75 73 |ons such| as caus|
|00002430| 61 6c 69 74 79 20 61 6e | 64 20 72 65 61 6c 20 74 |ality an|d real t|
|00002440| 69 6d 65 2e 20 20 50 61 | 72 74 69 61 6c 0a 6f 72 |ime.  Pa|rtial.or|
|00002450| 64 65 72 73 20 61 72 65 | 20 74 68 65 20 63 61 73 |ders are| the cas|
|00002460| 65 20 77 68 65 72 65 20 | 64 69 73 74 61 6e 63 65 |e where |distance|
|00002470| 73 20 61 72 65 20 74 77 | 6f 2d 76 61 6c 75 65 64 |s are tw|o-valued|
|00002480| 2c 20 69 2e 65 2e 20 61 | 20 62 69 6e 61 72 79 0a |, i.e. a| binary.|
|00002490| 72 65 6c 61 74 69 6f 6e | 2c 20 77 68 65 72 65 20 |relation|, where |
|000024a0| 74 68 65 20 74 72 69 61 | 6e 67 6c 65 20 69 6e 65 |the tria|ngle ine|
|000024b0| 71 75 61 6c 69 74 79 20 | 62 65 63 6f 6d 65 73 20 |quality |becomes |
|000024c0| 74 72 61 6e 73 69 74 69 | 76 69 74 79 20 61 6e 64 |transiti|vity and|
|000024d0| 20 69 74 73 0a 7a 65 72 | 6f 61 72 79 20 66 6f 72 | its.zer|oary for|
|000024e0| 6d 20 72 65 66 6c 65 78 | 69 76 69 74 79 2e 0a 0a |m reflex|ivity...|
|000024f0| 54 68 75 73 20 66 61 72 | 20 77 65 20 75 6e 64 65 |Thus far| we unde|
|00002500| 72 73 74 61 6e 64 20 6f | 6e 6c 79 20 74 68 65 20 |rstand o|nly the |
|00002510| 61 72 69 74 68 6d 65 74 | 69 63 20 6f 66 20 74 68 |arithmet|ic of th|
|00002520| 69 73 20 67 65 6e 65 72 | 61 6c 69 7a 61 74 69 6f |is gener|alizatio|
|00002530| 6e 20 6f 66 0a 70 61 72 | 74 69 61 6c 20 6f 72 64 |n of.par|tial ord|
|00002540| 65 72 73 2e 20 20 57 65 | 20 64 6f 20 6e 6f 74 20 |ers.  We| do not |
|00002550| 61 73 20 79 65 74 20 6b | 6e 6f 77 20 77 68 61 74 |as yet k|now what|
|00002560| 20 66 6f 72 6d 20 74 68 | 65 20 61 75 74 6f 6d 61 | form th|e automa|
|00002570| 74 6f 6e 20 64 75 61 6c | 20 74 6f 0a 61 20 67 65 |ton dual| to.a ge|
|00002580| 6e 65 72 61 6c 69 7a 65 | 64 20 6d 65 74 72 69 63 |neralize|d metric|
|00002590| 20 73 70 61 63 65 20 73 | 68 6f 75 6c 64 20 74 61 | space s|hould ta|
|000025a0| 6b 65 2c 20 6e 65 69 74 | 68 65 72 20 74 68 65 20 |ke, neit|her the |
|000025b0| 67 65 6f 6d 65 74 72 79 | 20 6f 66 20 74 68 61 74 |geometry| of that|
|000025c0| 0a 66 6f 72 6d 20 6e 6f | 72 20 74 68 65 20 6c 6f |.form no|r the lo|
|000025d0| 67 69 63 20 6f 66 20 74 | 68 61 74 20 64 75 61 6c |gic of t|hat dual|
|000025e0| 69 74 79 2e 20 20 57 65 | 20 77 6f 75 6c 64 20 62 |ity.  We| would b|
|000025f0| 65 20 64 65 6c 69 67 68 | 74 65 64 20 74 6f 20 73 |e deligh|ted to s|
|00002600| 65 65 20 61 0a 67 65 6e | 65 72 61 6c 69 7a 61 74 |ee a.gen|eralizat|
|00002610| 69 6f 6e 20 6f 66 20 74 | 68 65 20 76 65 72 79 20 |ion of t|he very |
|00002620| 61 74 74 72 61 63 74 69 | 76 65 20 6c 6f 67 69 63 |attracti|ve logic|
|00002630| 20 6f 66 20 65 76 65 6e | 74 20 61 6e 64 20 73 74 | of even|t and st|
|00002640| 61 74 65 20 73 70 61 63 | 65 73 0a 74 6f 20 74 68 |ate spac|es.to th|
|00002650| 65 73 65 20 67 65 6e 65 | 72 61 6c 69 7a 65 64 20 |ese gene|ralized |
|00002660| 6d 65 74 72 69 63 20 73 | 70 61 63 65 73 2e 20 20 |metric s|paces.  |
|00002670| 54 68 65 20 70 72 65 73 | 65 6e 74 20 70 61 70 65 |The pres|ent pape|
|00002680| 72 20 74 72 65 61 74 73 | 20 6f 6e 6c 79 20 74 68 |r treats| only th|
|00002690| 65 0a 70 61 72 74 69 61 | 6c 20 6f 72 64 65 72 20 |e.partia|l order |
|000026a0| 6d 6f 64 65 6c 20 6f 66 | 20 74 69 6d 65 20 61 6e |model of| time an|
|000026b0| 64 20 74 68 65 20 6e 6f | 74 69 6f 6e 20 6f 66 20 |d the no|tion of |
|000026c0| 63 6f 6e 66 6c 69 63 74 | 20 28 6f 66 20 61 6e 79 |conflict| (of any|
|000026d0| 20 61 72 69 74 79 29 2e | 0a 0a 5c 73 65 63 74 69 | arity).|..\secti|
|000026e0| 6f 6e 7b 41 72 69 74 68 | 6d 65 74 69 63 20 6f 66 |on{Arith|metic of|
|000026f0| 20 53 63 68 65 64 75 6c | 65 73 7d 0a 0a 5c 73 75 | Schedul|es}..\su|
|00002700| 62 73 65 63 74 69 6f 6e | 7b 43 61 72 64 69 6e 61 |bsection|{Cardina|
|00002710| 6c 20 61 6e 64 20 4f 72 | 64 69 6e 61 6c 20 41 72 |l and Or|dinal Ar|
|00002720| 69 74 68 6d 65 74 69 63 | 7d 0a 0a 54 68 65 20 70 |ithmetic|}..The p|
|00002730| 72 6f 67 65 6e 69 74 6f | 72 20 6f 66 20 74 68 65 |rogenito|r of the|
|00002740| 20 61 72 69 74 68 6d 65 | 74 69 63 20 6f 66 20 73 | arithme|tic of s|
|00002750| 63 68 65 64 75 6c 65 73 | 20 69 73 20 42 69 72 6b |chedules| is Birk|
|00002760| 68 6f 66 66 27 73 20 67 | 65 6e 65 72 61 6c 69 7a |hoff's g|eneraliz|
|00002770| 65 64 0a 61 72 69 74 68 | 6d 65 74 69 63 20 6f 66 |ed.arith|metic of|
|00002780| 20 70 6f 73 65 74 73 20 | 5c 63 69 74 65 7b 42 69 | posets |\cite{Bi|
|00002790| 72 6b 33 37 2c 42 69 72 | 6b 34 32 7d 20 61 73 20 |rk37,Bir|k42} as |
|000027a0| 61 20 63 6f 6d 6d 6f 6e | 20 67 65 6e 65 72 61 6c |a common| general|
|000027b0| 69 7a 61 74 69 6f 6e 20 | 6f 66 0a 63 61 72 64 69 |ization |of.cardi|
|000027c0| 6e 61 6c 20 61 6e 64 20 | 6f 72 64 69 6e 61 6c 20 |nal and |ordinal |
|000027d0| 61 72 69 74 68 6d 65 74 | 69 63 2e 20 20 54 68 65 |arithmet|ic.  The|
|000027e0| 20 72 65 6c 65 76 61 6e | 63 65 20 74 6f 20 63 6f | relevan|ce to co|
|000027f0| 6e 63 75 72 72 65 6e 63 | 79 20 69 73 20 74 68 61 |ncurrenc|y is tha|
|00002800| 74 0a 63 61 72 64 69 6e | 61 6c 73 2c 20 61 73 20 |t.cardin|als, as |
|00002810| 75 6e 6f 72 64 65 72 65 | 64 20 73 65 74 73 2c 20 |unordere|d sets, |
|00002820| 63 61 6e 20 62 65 20 69 | 6e 74 65 72 70 72 65 74 |can be i|nterpret|
|00002830| 65 64 20 61 73 20 63 6f | 6e 63 75 72 72 65 6e 74 |ed as co|ncurrent|
|00002840| 0a 73 63 68 65 64 75 6c | 65 73 20 77 68 69 6c 65 |.schedul|es while|
|00002850| 20 6f 72 64 69 6e 61 6c | 73 20 61 6e 64 20 6d 6f | ordinal|s and mo|
|00002860| 72 65 20 67 65 6e 65 72 | 61 6c 6c 79 20 63 68 61 |re gener|ally cha|
|00002870| 69 6e 73 20 63 6f 6e 73 | 74 69 74 75 74 65 0a 73 |ins cons|titute.s|
|00002880| 65 71 75 65 6e 74 69 61 | 6c 20 73 63 68 65 64 75 |equentia|l schedu|
|00002890| 6c 65 73 2e 20 20 43 61 | 72 64 69 6e 61 6c 20 61 |les.  Ca|rdinal a|
|000028a0| 64 64 69 74 69 6f 6e 20 | 28 64 69 73 6a 6f 69 6e |ddition |(disjoin|
|000028b0| 74 20 75 6e 69 6f 6e 29 | 20 24 41 2b 42 24 20 6f |t union)| $A+B$ o|
|000028c0| 66 0a 70 6f 73 65 74 73 | 20 73 65 72 76 65 73 20 |f.posets| serves |
|000028d0| 61 73 20 61 73 79 6e 63 | 68 72 6f 6e 6f 75 73 20 |as async|hronous |
|000028e0| 63 6f 6e 63 75 72 72 65 | 6e 63 65 20 28 64 6f 20 |concurre|nce (do |
|000028f0| 24 41 24 20 61 6e 64 20 | 24 42 24 0a 69 6e 64 65 |$A$ and |$B$.inde|
|00002900| 70 65 6e 64 65 6e 74 6c | 79 29 20 77 68 69 6c 65 |pendentl|y) while|
|00002910| 20 6f 72 64 69 6e 61 6c | 20 61 64 64 69 74 69 6f | ordinal| additio|
|00002920| 6e 20 28 63 6f 6e 63 61 | 74 65 6e 61 74 69 6f 6e |n (conca|tenation|
|00002930| 29 20 24 41 3b 42 24 20 | 69 73 0a 73 65 71 75 65 |) $A;B$ |is.seque|
|00002940| 6e 74 69 61 6c 20 63 6f | 6d 70 6f 73 69 74 69 6f |ntial co|mpositio|
|00002950| 6e 20 28 64 6f 20 24 41 | 24 20 74 68 65 6e 20 24 |n (do $A|$ then $|
|00002960| 42 24 29 2e 0a 0a 41 6e | 20 61 6c 67 65 62 72 61 |B$)...An| algebra|
|00002970| 20 6f 66 20 70 72 6f 63 | 65 73 73 65 73 20 73 69 | of proc|esses si|
|00002980| 6d 75 6c 74 61 6e 65 6f | 75 73 6c 79 20 64 65 66 |multaneo|usly def|
|00002990| 69 6e 65 73 20 61 20 70 | 61 72 61 6c 6c 65 6c 20 |ines a p|arallel |
|000029a0| 70 72 6f 67 72 61 6d 6d | 69 6e 67 0a 6c 61 6e 67 |programm|ing.lang|
|000029b0| 75 61 67 65 20 61 6e 64 | 20 65 71 75 69 70 73 20 |uage and| equips |
|000029c0| 69 74 20 77 69 74 68 20 | 61 20 73 65 6d 61 6e 74 |it with |a semant|
|000029d0| 69 63 73 2e 20 20 4d 69 | 6c 6e 65 72 2c 20 48 6f |ics.  Mi|lner, Ho|
|000029e0| 61 72 65 2c 20 42 65 72 | 67 73 74 72 61 20 61 6e |are, Ber|gstra an|
|000029f0| 64 0a 4b 6c 6f 70 2c 20 | 61 6e 64 20 6f 74 68 65 |d.Klop, |and othe|
|00002a00| 72 73 20 68 61 76 65 20 | 64 65 66 69 6e 65 64 20 |rs have |defined |
|00002a10| 76 61 72 69 6f 75 73 20 | 73 75 63 68 20 61 6c 67 |various |such alg|
|00002a20| 65 62 72 61 73 2e 20 20 | 57 68 69 6c 65 20 42 69 |ebras.  |While Bi|
|00002a30| 72 6b 68 6f 66 66 0a 61 | 72 69 74 68 6d 65 74 69 |rkhoff.a|rithmeti|
|00002a40| 63 20 6f 6e 6c 79 20 70 | 61 72 74 69 61 6c 6c 79 |c only p|artially|
|00002a50| 20 6d 65 65 74 73 20 74 | 68 65 20 6e 65 65 64 73 | meets t|he needs|
|00002a60| 20 6f 66 20 63 6f 6e 63 | 75 72 72 65 6e 74 20 70 | of conc|urrent p|
|00002a70| 72 6f 67 72 61 6d 6d 69 | 6e 67 2c 0a 6e 61 6d 65 |rogrammi|ng,.name|
|00002a80| 6c 79 20 77 68 61 74 20 | 77 65 20 74 68 69 6e 6b |ly what |we think|
|00002a90| 20 6f 66 20 61 73 20 74 | 68 65 20 60 60 63 6f 6e | of as t|he ``con|
|00002aa0| 6a 75 6e 63 74 69 76 65 | 27 27 20 70 6f 72 74 69 |junctive|'' porti|
|00002ab0| 6f 6e 2d 2d 2d 63 6f 6e | 63 75 72 72 65 6e 63 79 |on---con|currency|
|00002ac0| 0a 77 69 74 68 6f 75 74 | 20 6e 6f 6e 64 65 74 65 |.without| nondete|
|00002ad0| 72 6d 69 6e 69 73 6d 2d | 2d 2d 69 74 20 64 6f 65 |rminism-|--it doe|
|00002ae0| 73 20 68 61 76 65 20 61 | 20 73 75 66 66 69 63 69 |s have a| suffici|
|00002af0| 65 6e 74 6c 79 20 70 72 | 65 63 69 73 65 20 79 65 |ently pr|ecise ye|
|00002b00| 74 20 73 69 6d 70 6c 65 | 0a 6d 6f 64 65 6c 20 74 |t simple|.model t|
|00002b10| 68 65 6f 72 79 20 61 6e | 64 20 61 73 73 6f 63 69 |heory an|d associ|
|00002b20| 61 74 65 64 20 65 71 75 | 61 74 69 6f 6e 61 6c 20 |ated equ|ational |
|00002b30| 74 68 65 6f 72 79 20 61 | 73 20 74 6f 20 77 61 72 |theory a|s to war|
|00002b40| 72 61 6e 74 20 61 64 6d | 69 74 74 69 6e 67 0a 69 |rant adm|itting.i|
|00002b50| 74 20 61 73 20 6f 6e 65 | 20 63 6f 6d 70 6f 6e 65 |t as one| compone|
|00002b60| 6e 74 20 6f 66 20 74 68 | 65 20 66 6f 75 6e 64 61 |nt of th|e founda|
|00002b70| 74 69 6f 6e 73 20 6f 66 | 20 63 6f 6e 63 75 72 72 |tions of| concurr|
|00002b80| 65 6e 63 79 2e 0a 0a 42 | 69 72 6b 68 6f 66 66 20 |ency...B|irkhoff |
|00002b90| 61 72 69 74 68 6d 65 74 | 69 63 20 69 73 20 64 65 |arithmet|ic is de|
|00002ba0| 66 69 6e 65 64 20 6f 6e | 20 70 61 72 74 69 61 6c |fined on| partial|
|00002bb0| 6c 79 20 6f 72 64 65 72 | 65 64 20 73 65 74 73 2c |ly order|ed sets,|
|00002bc0| 20 63 6f 6e 73 69 64 65 | 72 65 64 20 74 6f 0a 62 | conside|red to.b|
|00002bd0| 65 20 64 65 66 69 6e 65 | 64 20 6f 6e 6c 79 20 75 |e define|d only u|
|00002be0| 70 20 74 6f 20 69 73 6f | 6d 6f 72 70 68 69 73 6d |p to iso|morphism|
|00002bf0| 2c 20 74 68 61 74 20 69 | 73 2c 20 24 41 5c 63 6f |, that i|s, $A\co|
|00002c00| 6e 67 20 42 24 20 69 6d | 70 6c 69 65 73 20 24 41 |ng B$ im|plies $A|
|00002c10| 3d 42 24 2e 0a 54 68 69 | 73 20 61 6c 6c 6f 77 73 |=B$..Thi|s allows|
|00002c20| 20 74 68 65 20 69 73 6f | 6d 6f 72 70 68 69 73 6d | the iso|morphism|
|00002c30| 20 24 41 2b 42 5c 63 6f | 6e 67 20 42 2b 41 24 20 | $A+B\co|ng B+A$ |
|00002c40| 74 6f 20 62 65 20 77 72 | 69 74 74 65 6e 20 61 73 |to be wr|itten as|
|00002c50| 20 24 41 2b 42 3d 42 2b | 41 24 2c 0a 61 6e 64 20 | $A+B=B+|A$,.and |
|00002c60| 24 28 41 5c 74 69 6d 65 | 73 20 42 29 5c 74 69 6d |$(A\time|s B)\tim|
|00002c70| 65 73 20 43 5c 63 6f 6e | 67 20 41 5c 74 69 6d 65 |es C\con|g A\time|
|00002c80| 73 20 28 42 5c 74 69 6d | 65 73 20 43 29 24 20 61 |s (B\tim|es C)$ a|
|00002c90| 73 20 24 28 41 5c 74 69 | 6d 65 73 0a 42 29 5c 74 |s $(A\ti|mes.B)\t|
|00002ca0| 69 6d 65 73 20 43 3d 41 | 5c 74 69 6d 65 73 20 28 |imes C=A|\times (|
|00002cb0| 42 5c 74 69 6d 65 73 20 | 43 29 24 2e 20 20 49 74 |B\times |C)$.  It|
|00002cc0| 20 61 6c 73 6f 20 69 6d | 70 6c 69 65 73 20 74 68 | also im|plies th|
|00002cd0| 61 74 20 74 68 65 72 65 | 20 69 73 20 6a 75 73 74 |at there| is just|
|00002ce0| 0a 6f 6e 65 20 75 6e 6f | 72 64 65 72 65 64 20 28 |.one uno|rdered (|
|00002cf0| 64 69 73 63 72 65 74 65 | 6c 79 20 6f 72 64 65 72 |discrete|ly order|
|00002d00| 65 64 29 20 73 65 74 20 | 6f 66 20 65 61 63 68 20 |ed) set |of each |
|00002d10| 63 61 72 64 69 6e 61 6c | 69 74 79 2c 20 77 68 69 |cardinal|ity, whi|
|00002d20| 63 68 20 77 65 0a 6d 61 | 79 20 74 68 65 6e 20 74 |ch we.ma|y then t|
|00002d30| 61 6b 65 20 74 6f 20 62 | 65 20 74 68 65 20 63 61 |ake to b|e the ca|
|00002d40| 72 64 69 6e 61 6c 73 2e | 20 20 53 69 6d 69 6c 61 |rdinals.|  Simila|
|00002d50| 72 6c 79 20 77 68 65 6e | 20 65 76 65 72 79 20 73 |rly when| every s|
|00002d60| 75 62 73 65 74 20 6f 66 | 20 61 0a 70 6f 73 65 74 |ubset of| a.poset|
|00002d70| 20 24 58 24 20 68 61 73 | 20 61 20 6c 65 61 73 74 | $X$ has| a least|
|00002d80| 20 65 6c 65 6d 65 6e 74 | 2c 20 74 68 61 74 20 69 | element|, that i|
|00002d90| 73 2c 20 69 73 20 77 65 | 6c 6c 2d 6f 72 64 65 72 |s, is we|ll-order|
|00002da0| 65 64 2c 20 77 65 20 74 | 61 6b 65 20 24 58 24 20 |ed, we t|ake $X$ |
|00002db0| 74 6f 0a 62 65 20 61 6e | 20 6f 72 64 69 6e 61 6c |to.be an| ordinal|
|00002dc0| 2e 0a 0a 54 68 65 20 6f | 70 65 72 61 74 69 6f 6e |...The o|peration|
|00002dd0| 73 20 6f 66 20 61 64 64 | 69 74 69 6f 6e 2c 20 6d |s of add|ition, m|
|00002de0| 75 6c 74 69 70 6c 69 63 | 61 74 69 6f 6e 2c 20 61 |ultiplic|ation, a|
|00002df0| 6e 64 20 65 78 70 6f 6e | 65 6e 74 69 61 74 69 6f |nd expon|entiatio|
|00002e00| 6e 20 65 61 63 68 0a 6f | 63 63 75 72 20 69 6e 20 |n each.o|ccur in |
|00002e10| 74 77 6f 20 66 6f 72 6d | 73 2c 20 63 61 72 64 69 |two form|s, cardi|
|00002e20| 6e 61 6c 20 61 6e 64 20 | 6f 72 64 69 6e 61 6c 2e |nal and |ordinal.|
|00002e30| 20 20 45 78 63 65 70 74 | 20 66 6f 72 20 6f 72 64 |  Except| for ord|
|00002e40| 69 6e 61 6c 0a 65 78 70 | 6f 6e 65 6e 74 69 61 74 |inal.exp|onentiat|
|00002e50| 69 6f 6e 2c 20 74 68 65 | 20 6f 70 65 72 61 74 69 |ion, the| operati|
|00002e60| 6f 6e 73 20 6f 66 20 61 | 20 67 69 76 65 6e 20 74 |ons of a| given t|
|00002e70| 79 70 65 20 70 72 65 73 | 65 72 76 65 20 70 6f 73 |ype pres|erve pos|
|00002e80| 65 74 73 20 6f 66 20 74 | 68 61 74 0a 74 79 70 65 |ets of t|hat.type|
|00002e90| 2c 20 61 6c 74 68 6f 75 | 67 68 20 74 68 65 79 20 |, althou|gh they |
|00002ea0| 61 72 65 20 64 65 66 69 | 6e 65 64 20 6f 6e 20 61 |are defi|ned on a|
|00002eb0| 6c 6c 20 70 6f 73 65 74 | 73 2e 0a 0a 49 6e 20 74 |ll poset|s...In t|
|00002ec0| 68 65 20 66 6f 6c 6c 6f | 77 69 6e 67 20 73 69 78 |he follo|wing six|
|00002ed0| 20 62 69 6e 61 72 79 20 | 6f 70 65 72 61 74 69 6f | binary |operatio|
|00002ee0| 6e 73 20 77 65 20 74 61 | 6b 65 20 74 68 65 20 74 |ns we ta|ke the t|
|00002ef0| 77 6f 20 61 72 67 75 6d | 65 6e 74 73 20 74 6f 20 |wo argum|ents to |
|00002f00| 62 65 0a 74 68 65 20 70 | 6f 73 65 74 73 20 24 41 |be.the p|osets $A|
|00002f10| 3d 28 58 2c 5c 6c 65 29 | 24 20 61 6e 64 20 24 42 |=(X,\le)|$ and $B|
|00002f20| 3d 28 59 2c 5c 70 72 65 | 63 65 71 29 24 2e 0a 0a |=(Y,\pre|ceq)$...|
|00002f30| 5c 73 65 74 6c 65 6e 67 | 74 68 7b 5c 75 6e 69 74 |\setleng|th{\unit|
|00002f40| 6c 65 6e 67 74 68 7d 7b | 30 2e 31 35 69 6e 7d 0a |length}{|0.15in}.|
|00002f50| 0a 54 68 65 20 63 61 72 | 64 69 6e 61 6c 20 73 75 |.The car|dinal su|
|00002f60| 6d 20 24 41 2b 42 24 20 | 69 73 20 73 69 6d 70 6c |m $A+B$ |is simpl|
|00002f70| 79 20 74 68 65 20 6a 75 | 78 74 61 70 6f 73 69 74 |y the ju|xtaposit|
|00002f80| 69 6f 6e 20 6f 66 20 24 | 41 24 20 61 6e 64 20 24 |ion of $|A$ and $|
|00002f90| 42 24 2e 20 46 6f 72 0a | 65 78 61 6d 70 6c 65 20 |B$. For.|example |
|00002fa0| 24 24 5c 70 69 63 32 31 | 7b 5c 70 30 31 5c 66 20 |$$\pic21|{\p01\f |
|00002fb0| 5c 70 32 31 5c 62 20 5c | 70 31 30 7d 2b 5c 70 69 |\p21\b \|p10}+\pi|
|00002fc0| 63 30 31 7b 5c 70 30 31 | 5c 64 20 20 5c 70 30 30 |c01{\p01|\d  \p00|
|00002fd0| 7d 7e 7e 3d 7e 7e 0a 5c | 70 69 63 32 31 7b 5c 70 |}~~=~~.\|pic21{\p|
|00002fe0| 30 31 5c 66 20 5c 70 32 | 31 5c 62 20 5c 70 31 30 |01\f \p2|1\b \p10|
|00002ff0| 7d 7e 5c 70 69 63 30 31 | 7b 5c 70 30 31 5c 64 20 |}~\pic01|{\p01\d |
|00003000| 20 5c 70 30 30 7d 2e 24 | 24 20 46 6f 72 6d 61 6c | \p00}.$|$ Formal|
|00003010| 6c 79 2c 0a 24 41 2b 42 | 3d 28 58 2b 59 2c 5c 6c |ly,.$A+B|=(X+Y,\l|
|00003020| 65 5f 30 5c 63 75 70 5c | 70 72 65 63 65 71 5f 31 |e_0\cup\|preceq_1|
|00003030| 29 24 20 77 68 65 72 65 | 20 24 58 2b 59 24 20 64 |)$ where| $X+Y$ d|
|00003040| 65 6e 6f 74 65 73 0a 24 | 28 58 5c 74 69 6d 65 73 |enotes.$|(X\times|
|00003050| 5c 7b 30 5c 7d 29 5c 63 | 75 70 28 59 5c 74 69 6d |\{0\})\c|up(Y\tim|
|00003060| 65 73 5c 7b 31 5c 7d 29 | 24 2c 20 24 5c 6c 65 5f |es\{1\})|$, $\le_|
|00003070| 30 24 20 70 61 72 74 69 | 61 6c 6c 79 20 6f 72 64 |0$ parti|ally ord|
|00003080| 65 72 73 0a 24 58 5c 74 | 69 6d 65 73 5c 7b 30 5c |ers.$X\t|imes\{0\|
|00003090| 7d 24 20 74 6f 20 6d 61 | 6b 65 20 24 28 58 5c 74 |}$ to ma|ke $(X\t|
|000030a0| 69 6d 65 73 5c 7b 30 5c | 7d 2c 5c 6c 65 5f 30 29 |imes\{0\|},\le_0)|
|000030b0| 24 20 69 73 6f 6d 6f 72 | 70 68 69 63 20 74 6f 20 |$ isomor|phic to |
|000030c0| 24 41 24 20 76 69 61 20 | 61 6e 0a 69 73 6f 6d 6f |$A$ via |an.isomo|
|000030d0| 72 70 68 69 73 6d 20 74 | 68 61 74 20 70 61 69 72 |rphism t|hat pair|
|000030e0| 73 20 24 28 78 2c 30 29 | 24 20 77 69 74 68 20 24 |s $(x,0)|$ with $|
|000030f0| 78 24 2c 20 61 6e 64 20 | 24 28 59 5c 74 69 6d 65 |x$, and |$(Y\time|
|00003100| 73 5c 7b 31 5c 7d 2c 5c | 6c 65 5f 31 29 24 20 69 |s\{1\},\|le_1)$ i|
|00003110| 73 0a 73 69 6d 69 6c 61 | 72 6c 79 20 69 73 6f 6d |s.simila|rly isom|
|00003120| 6f 72 70 68 69 63 20 74 | 6f 20 24 42 24 2e 0a 0a |orphic t|o $B$...|
|00003130| 41 73 20 61 6e 20 6f 70 | 65 72 61 74 69 6f 6e 20 |As an op|eration |
|00003140| 6f 6e 20 73 63 68 65 64 | 75 6c 65 73 2c 20 63 61 |on sched|ules, ca|
|00003150| 72 64 69 6e 61 6c 20 73 | 75 6d 20 69 73 20 61 73 |rdinal s|um is as|
|00003160| 79 6e 63 68 72 6f 6e 6f | 75 73 20 63 6f 6e 63 75 |ynchrono|us concu|
|00003170| 72 72 65 6e 63 65 2e 0a | 0a 54 68 65 20 63 61 72 |rrence..|.The car|
|00003180| 64 69 6e 61 6c 20 70 72 | 6f 64 75 63 74 20 24 41 |dinal pr|oduct $A|
|00003190| 5c 74 69 6d 65 73 20 42 | 24 20 28 42 69 72 6b 68 |\times B|$ (Birkh|
|000031a0| 6f 66 66 20 77 72 69 74 | 65 73 20 24 41 42 24 29 |off writ|es $AB$)|
|000031b0| 20 69 73 20 24 28 58 5c | 74 69 6d 65 73 0a 59 2c | is $(X\|times.Y,|
|000031c0| 5c 73 71 73 75 62 73 65 | 74 65 71 29 24 2c 20 77 |\sqsubse|teq)$, w|
|000031d0| 68 65 72 65 20 24 28 78 | 2c 79 29 5c 73 71 73 75 |here $(x|,y)\sqsu|
|000031e0| 62 73 65 74 65 71 28 78 | 27 2c 79 27 29 24 20 6a |bseteq(x|',y')$ j|
|000031f0| 75 73 74 20 77 68 65 6e | 20 24 78 5c 6c 65 20 78 |ust when| $x\le x|
|00003200| 27 24 0a 61 6e 64 20 24 | 79 5c 70 72 65 63 65 71 |'$.and $|y\preceq|
|00003210| 20 79 27 24 2e 20 20 46 | 6f 72 20 65 78 61 6d 70 | y'$.  F|or examp|
|00003220| 6c 65 0a 24 24 5c 70 69 | 63 32 31 7b 5c 70 30 31 |le.$$\pi|c21{\p01|
|00003230| 5c 66 20 5c 70 32 31 5c | 62 20 5c 70 31 30 7d 5c |\f \p21\|b \p10}\|
|00003240| 74 69 6d 65 73 5c 70 69 | 63 30 31 7b 5c 70 30 31 |times\pi|c01{\p01|
|00003250| 5c 64 20 20 5c 70 30 30 | 7d 3d 0a 5c 70 69 63 32 |\d  \p00|}=.\pic2|
|00003260| 32 7b 5c 70 30 32 5c 64 | 5c 66 20 5c 70 32 32 5c |2{\p02\d|\f \p22\|
|00003270| 62 5c 64 20 5c 70 30 31 | 5c 66 20 20 5c 70 31 31 |b\d \p01|\f  \p11|
|00003280| 5c 64 20 20 5c 70 32 31 | 5c 62 20 5c 70 31 30 7d |\d  \p21|\b \p10}|
|00003290| 0a 5c 6d 62 6f 78 7b 7e | 7e 7e 61 6e 64 7e 7e 7e |.\mbox{~|~~and~~~|
|000032a0| 7d 0a 5c 70 69 63 32 31 | 7b 5c 70 30 31 5c 66 20 |}.\pic21|{\p01\f |
|000032b0| 5c 70 32 31 5c 62 20 5c | 70 31 30 7d 5c 74 69 6d |\p21\b \|p10}\tim|
|000032c0| 65 73 5c 70 69 63 31 30 | 7b 5c 70 30 30 20 5c 70 |es\pic10|{\p00 \p|
|000032d0| 31 30 7d 7e 7e 3d 7e 7e | 0a 5c 70 69 63 32 31 7b |10}~~=~~|.\pic21{|
|000032e0| 5c 70 30 31 5c 66 20 5c | 70 32 31 5c 62 20 5c 70 |\p01\f \|p21\b \p|
|000032f0| 31 30 7d 5c 70 69 63 32 | 31 7b 5c 70 30 31 5c 66 |10}\pic2|1{\p01\f|
|00003300| 20 5c 70 32 31 5c 62 20 | 5c 70 31 30 7d 2e 24 24 | \p21\b |\p10}.$$|
|00003310| 0a 0a 54 68 65 20 63 61 | 72 64 69 6e 61 6c 20 70 |..The ca|rdinal p|
|00003320| 72 6f 64 75 63 74 20 6f | 66 20 73 63 68 65 64 75 |roduct o|f schedu|
|00003330| 6c 65 73 20 69 73 20 7b | 5c 69 74 20 6f 72 74 68 |les is {|\it orth|
|00003340| 6f 63 75 72 72 65 6e 63 | 65 7d 20 6f 72 20 7b 5c |ocurrenc|e} or {\|
|00003350| 69 74 0a 69 6e 74 65 72 | 61 63 74 69 6f 6e 7d 2c |it.inter|action},|
|00003360| 20 64 65 73 63 72 69 62 | 69 6e 67 20 74 68 65 20 | describ|ing the |
|00003370| 66 6c 6f 77 20 6f 66 20 | 24 41 24 20 74 68 72 6f |flow of |$A$ thro|
|00003380| 75 67 68 20 24 42 24 2c | 20 61 20 73 79 6d 6d 65 |ugh $B$,| a symme|
|00003390| 74 72 69 63 20 66 6f 72 | 6d 0a 6f 66 20 69 6e 74 |tric for|m.of int|
|000033a0| 65 72 61 63 74 69 6f 6e | 2e 20 20 45 76 65 72 79 |eraction|.  Every|
|000033b0| 20 65 76 65 6e 74 20 6f | 66 20 24 41 24 20 69 6e | event o|f $A$ in|
|000033c0| 74 65 72 61 63 74 73 20 | 77 69 74 68 20 65 76 65 |teracts |with eve|
|000033d0| 72 79 20 65 76 65 6e 74 | 20 6f 66 20 24 42 24 2c |ry event| of $B$,|
|000033e0| 0a 65 61 63 68 20 73 75 | 63 68 20 69 6e 74 65 72 |.each su|ch inter|
|000033f0| 61 63 74 69 6f 6e 20 63 | 6f 6e 73 74 69 74 75 74 |action c|onstitut|
|00003400| 69 6e 67 20 61 6e 20 65 | 76 65 6e 74 20 6f 66 20 |ing an e|vent of |
|00003410| 24 41 5c 74 69 6d 65 73 | 20 42 24 2e 20 20 46 6f |$A\times| B$.  Fo|
|00003420| 72 0a 65 78 61 6d 70 6c | 65 20 74 68 65 20 69 6e |r.exampl|e the in|
|00003430| 74 65 72 61 63 74 69 6f | 6e 20 6f 66 20 74 68 72 |teractio|n of thr|
|00003440| 65 65 20 74 72 61 69 6e | 73 20 70 61 73 73 69 6e |ee train|s passin|
|00003450| 67 20 74 68 72 6f 75 67 | 68 20 66 6f 75 72 20 73 |g throug|h four s|
|00003460| 74 61 74 69 6f 6e 73 0a | 63 6f 6e 74 61 69 6e 73 |tations.|contains|
|00003470| 20 74 77 65 6c 76 65 20 | 65 76 65 6e 74 73 2c 20 | twelve |events, |
|00003480| 6f 72 64 65 72 65 64 20 | 69 6e 20 74 68 65 20 73 |ordered |in the s|
|00003490| 68 61 70 65 20 6f 66 20 | 61 20 24 33 5c 74 69 6d |hape of |a $3\tim|
|000034a0| 65 73 20 34 24 0a 72 65 | 63 74 61 6e 67 6c 65 2e |es 4$.re|ctangle.|
|000034b0| 0a 0a 54 68 65 20 63 61 | 72 64 69 6e 61 6c 20 65 |..The ca|rdinal e|
|000034c0| 78 70 6f 6e 65 6e 74 69 | 61 74 69 6f 6e 20 24 42 |xponenti|ation $B|
|000034d0| 5e 41 24 20 63 6f 6e 73 | 69 73 74 73 20 6f 66 20 |^A$ cons|ists of |
|000034e0| 74 68 65 20 6d 6f 6e 6f | 74 6f 6e 65 20 66 75 6e |the mono|tone fun|
|000034f0| 63 74 69 6f 6e 73 0a 66 | 72 6f 6d 20 24 41 24 20 |ctions.f|rom $A$ |
|00003500| 74 6f 20 24 42 24 2c 20 | 6f 72 64 65 72 65 64 20 |to $B$, |ordered |
|00003510| 70 6f 69 6e 74 77 69 73 | 65 3a 20 24 66 5c 73 71 |pointwis|e: $f\sq|
|00003520| 73 75 62 73 65 74 65 71 | 20 67 24 20 6a 75 73 74 |subseteq| g$ just|
|00003530| 20 77 68 65 6e 0a 24 66 | 28 78 29 5c 70 72 65 63 | when.$f|(x)\prec|
|00003540| 65 71 20 67 28 78 29 24 | 20 66 6f 72 20 61 6c 6c |eq g(x)$| for all|
|00003550| 20 24 78 24 20 69 6e 20 | 24 41 24 2e 20 20 46 6f | $x$ in |$A$.  Fo|
|00003560| 72 20 65 78 61 6d 70 6c | 65 0a 24 24 5c 70 69 63 |r exampl|e.$$\pic|
|00003570| 32 31 7b 5c 70 30 31 5c | 66 20 5c 70 32 31 5c 62 |21{\p01\|f \p21\b|
|00003580| 20 5c 70 31 30 7d 5e 7b | 5c 70 69 63 30 31 7b 5c | \p10}^{|\pic01{\|
|00003590| 70 30 31 5c 64 20 20 5c | 70 30 30 7d 7d 0a 7e 7e |p01\d  \|p00}}.~~|
|000035a0| 3d 7e 7e 0a 5c 70 69 63 | 33 32 7b 5c 70 30 32 5c |=~~.\pic|32{\p02\|
|000035b0| 64 20 5c 70 32 32 5c 64 | 20 5c 70 30 31 5c 66 20 |d \p22\d| \p01\f |
|000035c0| 5c 70 32 31 5c 62 20 20 | 5c 70 31 30 7d 0a 5c 6d |\p21\b  |\p10}.\m|
|000035d0| 62 6f 78 7b 7e 7e 7e 77 | 68 69 6c 65 7e 7e 7e 7d |box{~~~w|hile~~~}|
|000035e0| 0a 5c 70 69 63 30 31 7b | 5c 70 30 31 5c 64 20 20 |.\pic01{|\p01\d  |
|000035f0| 5c 70 30 30 7d 5e 7b 5c | 70 69 63 32 31 7b 5c 70 |\p00}^{\|pic21{\p|
|00003600| 30 31 5c 66 20 5c 70 32 | 31 5c 62 20 5c 70 31 30 |01\f \p2|1\b \p10|
|00003610| 7d 7d 0a 7e 7e 3d 7e 7e | 0a 5c 70 69 63 32 33 7b |}}.~~=~~|.\pic23{|
|00003620| 5c 70 31 33 5c 64 20 5c | 70 31 32 5c 62 5c 66 20 |\p13\d \|p12\b\f |
|00003630| 5c 70 30 31 5c 66 20 5c | 70 32 31 5c 62 20 5c 70 |\p01\f \|p21\b \p|
|00003640| 31 30 7d 2e 24 24 0a 42 | 69 72 6b 68 6f 66 66 20 |10}.$$.B|irkhoff |
|00003650| 67 69 76 65 73 20 61 20 | 6e 75 6d 62 65 72 20 6f |gives a |number o|
|00003660| 66 20 6c 61 77 73 20 66 | 6f 72 20 74 68 65 20 63 |f laws f|or the c|
|00003670| 61 72 64 69 6e 61 6c 20 | 6f 70 65 72 61 74 69 6f |ardinal |operatio|
|00003680| 6e 73 2c 20 61 6c 6c 20 | 6f 66 0a 77 68 69 63 68 |ns, all |of.which|
|00003690| 20 68 6f 77 65 76 65 72 | 20 61 72 65 20 69 6e 66 | however| are inf|
|000036a0| 65 72 72 61 62 6c 65 20 | 61 73 20 74 68 65 20 63 |errable |as the c|
|000036b0| 6f 6e 73 65 71 75 65 6e | 63 65 73 20 6f 66 20 74 |onsequen|ces of t|
|000036c0| 68 65 20 63 61 74 65 67 | 6f 72 79 20 24 5c 50 6f |he categ|ory $\Po|
|000036d0| 73 24 0a 6f 66 20 70 61 | 72 74 69 61 6c 6c 79 20 |s$.of pa|rtially |
|000036e0| 6f 72 64 65 72 65 64 20 | 73 65 74 73 20 62 65 69 |ordered |sets bei|
|000036f0| 6e 67 20 61 20 63 61 72 | 74 65 73 69 61 6e 20 63 |ng a car|tesian c|
|00003700| 6c 6f 73 65 64 20 63 61 | 74 65 67 6f 72 79 20 77 |losed ca|tegory w|
|00003710| 69 74 68 0a 61 64 64 69 | 74 69 6f 6e 20 28 63 6f |ith.addi|tion (co|
|00003720| 70 72 6f 64 75 63 74 73 | 20 24 41 2b 42 24 29 2e |products| $A+B$).|
|00003730| 20 20 46 6f 72 20 65 78 | 61 6d 70 6c 65 20 61 64 |  For ex|ample ad|
|00003740| 64 69 74 69 6f 6e 20 61 | 6e 64 20 6d 75 6c 74 69 |dition a|nd multi|
|00003750| 70 6c 69 63 61 74 69 6f | 6e 0a 61 72 65 20 61 73 |plicatio|n.are as|
|00003760| 73 6f 63 69 61 74 69 76 | 65 20 61 6e 64 20 63 6f |sociativ|e and co|
|00003770| 6d 6d 75 74 61 74 69 76 | 65 2c 20 6d 75 6c 74 69 |mmutativ|e, multi|
|00003780| 70 6c 69 63 61 74 69 6f | 6e 20 64 69 73 74 72 69 |plicatio|n distri|
|00003790| 62 75 74 65 73 20 6f 76 | 65 72 0a 61 64 64 69 74 |butes ov|er.addit|
|000037a0| 69 6f 6e 2c 20 61 6e 64 | 20 24 41 5e 7b 42 2b 43 |ion, and| $A^{B+C|
|000037b0| 7d 3d 41 5e 42 5c 74 69 | 6d 65 73 20 41 5e 43 24 |}=A^B\ti|mes A^C$|
|000037c0| 2c 20 24 28 41 5c 74 69 | 6d 65 73 20 42 29 5e 43 |, $(A\ti|mes B)^C|
|000037d0| 3d 41 5e 43 5c 74 69 6d | 65 73 20 42 5e 43 24 2c |=A^C\tim|es B^C$,|
|000037e0| 0a 24 28 41 5e 42 29 5e | 43 3d 41 5e 7b 42 5c 74 |.$(A^B)^|C=A^{B\t|
|000037f0| 69 6d 65 73 20 43 7d 24 | 2c 20 24 41 5e 31 3d 41 |imes C}$|, $A^1=A|
|00003800| 24 2c 20 61 6e 64 20 24 | 31 5e 41 3d 31 24 2e 0a |$, and $|1^A=1$..|
|00003810| 0a 50 6f 73 65 74 73 20 | 61 72 65 20 76 65 72 79 |.Posets |are very|
|00003820| 20 6f 62 6c 69 67 69 6e | 67 20 69 6e 20 74 68 69 | obligin|g in thi|
|00003830| 73 20 77 61 79 2c 20 77 | 68 69 63 68 20 69 73 20 |s way, w|hich is |
|00003840| 6f 6e 65 20 74 68 69 6e | 67 20 74 68 61 74 20 6d |one thin|g that m|
|00003850| 61 6b 65 73 0a 74 68 65 | 6d 20 73 6f 20 61 74 74 |akes.the|m so att|
|00003860| 72 61 63 74 69 76 65 20 | 66 6f 72 20 63 6f 6e 63 |ractive |for conc|
|00003870| 75 72 72 65 6e 74 20 70 | 72 6f 67 72 61 6d 6d 69 |urrent p|rogrammi|
|00003880| 6e 67 2e 20 20 54 68 65 | 20 63 6f 72 72 65 73 70 |ng.  The| corresp|
|00003890| 6f 6e 64 69 6e 67 0a 73 | 69 74 75 61 74 69 6f 6e |onding.s|ituation|
|000038a0| 20 66 6f 72 20 74 68 65 | 20 63 61 74 65 67 6f 72 | for the| categor|
|000038b0| 79 20 6f 66 20 63 68 61 | 69 6e 73 20 28 6c 69 6e |y of cha|ins (lin|
|000038c0| 65 61 72 20 6f 72 64 65 | 72 73 29 20 61 6e 64 20 |ear orde|rs) and |
|000038d0| 74 68 65 69 72 20 6d 6f | 6e 6f 74 6f 6e 65 0a 66 |their mo|notone.f|
|000038e0| 75 6e 63 74 69 6f 6e 73 | 20 69 73 20 6d 75 63 68 |unctions| is much|
|000038f0| 20 6c 65 73 73 20 73 61 | 74 69 73 66 61 63 74 6f | less sa|tisfacto|
|00003900| 72 79 2e 20 20 4e 65 69 | 74 68 65 72 20 70 72 6f |ry.  Nei|ther pro|
|00003910| 64 75 63 74 20 6e 6f 72 | 20 63 6f 70 72 6f 64 75 |duct nor| coprodu|
|00003920| 63 74 0a 65 78 69 73 74 | 2c 20 74 68 61 74 20 69 |ct.exist|, that i|
|00003930| 73 2c 20 63 68 61 69 6e | 73 20 63 61 6e 6e 6f 74 |s, chain|s cannot|
|00003940| 20 62 65 20 61 64 64 65 | 64 20 61 6e 64 20 6d 75 | be adde|d and mu|
|00003950| 6c 74 69 70 6c 69 65 64 | 20 74 68 65 20 77 61 79 |ltiplied| the way|
|00003960| 20 70 6f 73 65 74 73 0a | 63 61 6e 2e 20 20 4f 6e | posets.|can.  On|
|00003970| 65 20 63 61 6e 20 63 6f | 6e 63 61 74 65 6e 61 74 |e can co|ncatenat|
|00003980| 65 20 63 68 61 69 6e 73 | 2c 20 61 6e 20 6f 70 65 |e chains|, an ope|
|00003990| 72 61 74 69 6f 6e 20 77 | 65 20 61 72 65 20 61 62 |ration w|e are ab|
|000039a0| 6f 75 74 20 74 6f 20 6d | 65 65 74 20 61 73 0a 6f |out to m|eet as.o|
|000039b0| 72 64 69 6e 61 6c 20 73 | 75 6d 2c 20 62 75 74 20 |rdinal s|um, but |
|000039c0| 74 68 69 73 20 69 73 20 | 61 20 73 65 71 75 65 6e |this is |a sequen|
|000039d0| 74 69 61 6c 20 6f 70 65 | 72 61 74 69 6f 6e 20 6f |tial ope|ration o|
|000039e0| 6e 20 73 65 71 75 65 6e | 74 69 61 6c 20 6f 62 6a |n sequen|tial obj|
|000039f0| 65 63 74 73 0a 61 6e 64 | 20 64 6f 65 73 20 6e 6f |ects.and| does no|
|00003a00| 74 20 65 78 74 65 6e 64 | 20 6e 61 74 75 72 61 6c |t extend| natural|
|00003a10| 6c 79 20 74 6f 20 63 6f | 6e 63 75 72 72 65 6e 63 |ly to co|ncurrenc|
|00003a20| 79 2e 0a 0a 54 68 65 20 | 6f 72 64 69 6e 61 6c 20 |y...The |ordinal |
|00003a30| 73 75 6d 20 24 41 3b 42 | 24 2c 20 6e 6f 74 61 74 |sum $A;B|$, notat|
|00003a40| 65 64 20 24 42 5c 6f 70 | 6c 75 73 20 41 24 20 62 |ed $B\op|lus A$ b|
|00003a50| 79 20 42 69 72 6b 68 6f | 66 66 20 77 68 6f 20 77 |y Birkho|ff who w|
|00003a60| 72 6f 74 65 20 24 78 3e | 79 24 0a 69 6e 20 70 72 |rote $x>|y$.in pr|
|00003a70| 65 66 65 72 65 6e 63 65 | 20 74 6f 20 24 79 3c 78 |eference| to $y<x|
|00003a80| 24 2c 2c 20 69 73 20 24 | 41 2b 42 24 20 77 69 74 |$,, is $|A+B$ wit|
|00003a90| 68 20 69 74 73 20 6f 72 | 64 65 72 20 61 75 67 6d |h its or|der augm|
|00003aa0| 65 6e 74 65 64 20 77 69 | 74 68 0a 24 58 5c 74 69 |ented wi|th.$X\ti|
|00003ab0| 6d 65 73 20 59 24 2c 20 | 74 68 61 74 20 69 73 2c |mes Y$, |that is,|
|00003ac0| 20 77 69 74 68 20 74 68 | 6f 73 65 20 70 61 69 72 | with th|ose pair|
|00003ad0| 73 20 24 28 78 2c 30 29 | 5c 73 71 73 75 62 73 65 |s $(x,0)|\sqsubse|
|00003ae0| 74 65 71 28 79 2c 31 29 | 24 20 66 6f 72 20 61 6c |teq(y,1)|$ for al|
|00003af0| 6c 0a 24 78 5c 69 6e 20 | 58 2c 79 5c 69 6e 20 59 |l.$x\in |X,y\in Y|
|00003b00| 24 2e 20 20 46 6f 72 20 | 65 78 61 6d 70 6c 65 0a |$.  For |example.|
|00003b10| 24 24 5c 70 69 63 32 31 | 7b 5c 70 30 31 5c 66 20 |$$\pic21|{\p01\f |
|00003b20| 5c 70 32 31 5c 62 20 5c | 70 31 30 7d 3b 5c 70 69 |\p21\b \|p10};\pi|
|00003b30| 63 30 31 7b 5c 70 30 31 | 5c 64 20 20 5c 70 30 30 |c01{\p01|\d  \p00|
|00003b40| 7d 7e 7e 3d 7e 7e 0a 5c | 70 69 63 32 33 7b 5c 70 |}~~=~~.\|pic23{\p|
|00003b50| 31 33 5c 64 20 5c 70 31 | 32 5c 62 5c 66 20 5c 70 |13\d \p1|2\b\f \p|
|00003b60| 30 31 5c 66 20 5c 70 32 | 31 5c 62 20 5c 70 31 30 |01\f \p2|1\b \p10|
|00003b70| 7d 0a 5c 6d 62 6f 78 7b | 7e 7e 7e 77 68 69 6c 65 |}.\mbox{|~~~while|
|00003b80| 7e 7e 7e 7d 0a 5c 70 69 | 63 30 31 7b 5c 70 30 31 |~~~}.\pi|c01{\p01|
|00003b90| 5c 64 20 20 5c 70 30 30 | 7d 3b 5c 70 69 63 32 31 |\d  \p00|};\pic21|
|00003ba0| 7b 5c 70 30 31 5c 66 20 | 5c 70 32 31 5c 62 20 5c |{\p01\f |\p21\b \|
|00003bb0| 70 31 30 7d 7e 7e 3d 7e | 7e 0a 5c 70 69 63 32 33 |p10}~~=~|~.\pic23|
|00003bc0| 7b 5c 70 30 33 5c 66 20 | 5c 70 32 33 5c 62 20 5c |{\p03\f |\p23\b \|
|00003bd0| 70 31 32 5c 64 20 5c 70 | 31 31 5c 64 20 5c 70 31 |p12\d \p|11\d \p1|
|00003be0| 30 7d 0a 24 24 0a 41 73 | 20 61 6e 20 6f 70 65 72 |0}.$$.As| an oper|
|00003bf0| 61 74 69 6f 6e 20 6f 6e | 20 73 63 68 65 64 75 6c |ation on| schedul|
|00003c00| 65 73 20 6f 72 64 69 6e | 61 6c 20 73 75 6d 20 69 |es ordin|al sum i|
|00003c10| 73 20 63 6f 6e 63 61 74 | 65 6e 61 74 69 6f 6e 3a |s concat|enation:|
|00003c20| 20 64 6f 20 24 41 24 20 | 74 68 65 6e 0a 24 42 24 | do $A$ |then.$B$|
|00003c30| 2e 0a 0a 4f 72 64 69 6e | 61 6c 20 73 75 6d 20 69 |...Ordin|al sum i|
|00003c40| 73 20 61 73 73 6f 63 69 | 61 74 69 76 65 20 61 6e |s associ|ative an|
|00003c50| 64 20 68 61 73 20 74 68 | 65 20 73 61 6d 65 20 69 |d has th|e same i|
|00003c60| 64 65 6e 74 69 74 79 20 | 61 73 20 63 61 72 64 69 |dentity |as cardi|
|00003c70| 6e 61 6c 20 73 75 6d 2c | 0a 6e 61 6d 65 6c 79 20 |nal sum,|.namely |
|00003c80| 74 68 65 20 65 6d 70 74 | 79 20 70 6f 73 65 74 20 |the empt|y poset |
|00003c90| 30 20 28 77 68 69 63 68 | 20 42 69 72 6b 68 6f 66 |0 (which| Birkhof|
|00003ca0| 66 20 64 69 73 61 6c 6c | 6f 77 73 20 6f 6e 20 74 |f disall|ows on t|
|00003cb0| 68 65 20 67 72 6f 75 6e | 64 73 20 74 68 61 74 0a |he groun|ds that.|
|00003cc0| 24 30 5e 30 24 20 63 6f | 75 6c 64 20 62 65 20 65 |$0^0$ co|uld be e|
|00003cd0| 69 74 68 65 72 20 30 20 | 6f 72 20 31 20 61 6e 64 |ither 0 |or 1 and|
|00003ce0| 20 74 68 61 74 20 31 20 | 77 6f 75 6c 64 20 6e 6f | that 1 |would no|
|00003cf0| 74 20 62 65 20 61 20 71 | 75 6f 74 69 65 6e 74 20 |t be a q|uotient |
|00003d00| 6f 72 0a 60 60 68 6f 6d | 6f 6e 75 6d 62 65 72 27 |or.``hom|onumber'|
|00003d10| 27 20 6f 66 20 30 2c 20 | 62 6f 74 68 20 66 61 6c |' of 0, |both fal|
|00003d20| 73 65 20 62 79 20 74 6f | 64 61 79 27 73 20 73 74 |se by to|day's st|
|00003d30| 61 6e 64 61 72 64 73 29 | 2e 20 20 48 6f 77 65 76 |andards)|.  Howev|
|00003d40| 65 72 20 69 74 20 69 73 | 0a 6e 6f 74 20 63 6f 6d |er it is|.not com|
|00003d50| 6d 75 74 61 74 69 76 65 | 2e 0a 0a 54 68 65 20 6f |mutative|...The o|
|00003d60| 72 64 69 6e 61 6c 20 6f | 72 20 6c 65 78 69 63 6f |rdinal o|r lexico|
|00003d70| 67 72 61 70 68 69 63 20 | 70 72 6f 64 75 63 74 20 |graphic |product |
|00003d80| 24 41 5c 63 69 72 63 20 | 42 24 20 69 73 20 24 41 |$A\circ |B$ is $A|
|00003d90| 5c 74 69 6d 65 73 20 42 | 24 20 77 69 74 68 20 69 |\times B|$ with i|
|00003da0| 74 73 0a 6f 72 64 65 72 | 20 61 75 67 6d 65 6e 74 |ts.order| augment|
|00003db0| 65 64 20 77 69 74 68 20 | 74 68 6f 73 65 20 70 61 |ed with |those pa|
|00003dc0| 69 72 73 20 24 28 78 2c | 79 29 5c 73 71 73 75 62 |irs $(x,|y)\sqsub|
|00003dd0| 73 65 74 65 71 28 78 27 | 2c 79 27 29 24 20 66 6f |seteq(x'|,y')$ fo|
|00003de0| 72 20 77 68 69 63 68 20 | 24 78 3c 78 27 24 2e 0a |r which |$x<x'$..|
|00003df0| 46 6f 72 20 65 78 61 6d | 70 6c 65 20 24 24 5c 70 |For exam|ple $$\p|
|00003e00| 69 63 32 31 7b 5c 70 30 | 31 5c 66 20 5c 70 32 31 |ic21{\p0|1\f \p21|
|00003e10| 5c 62 20 5c 70 31 30 7d | 5c 63 69 72 63 5c 70 69 |\b \p10}|\circ\pi|
|00003e20| 63 30 31 7b 5c 70 30 31 | 5c 64 20 20 5c 70 30 30 |c01{\p01|\d  \p00|
|00003e30| 7d 7e 7e 3d 7e 7e 0a 5c | 70 69 63 32 33 7b 5c 70 |}~~=~~.\|pic23{\p|
|00003e40| 30 33 5c 64 20 5c 70 32 | 33 5c 64 20 5c 70 30 32 |03\d \p2|3\d \p02|
|00003e50| 5c 66 20 5c 70 32 32 5c | 62 20 5c 70 31 31 5c 64 |\f \p22\|b \p11\d|
|00003e60| 20 5c 70 31 30 7d 0a 5c | 6d 62 6f 78 7b 7e 7e 7e | \p10}.\|mbox{~~~|
|00003e70| 77 68 69 6c 65 7e 7e 7e | 7d 0a 5c 70 69 63 30 31 |while~~~|}.\pic01|
|00003e80| 7b 5c 70 30 31 5c 64 20 | 20 5c 70 30 30 7d 5c 63 |{\p01\d | \p00}\c|
|00003e90| 69 72 63 5c 70 69 63 32 | 31 7b 5c 70 30 31 5c 66 |irc\pic2|1{\p01\f|
|00003ea0| 20 5c 70 32 31 5c 62 20 | 5c 70 31 30 7d 7e 7e 3d | \p21\b |\p10}~~=|
|00003eb0| 7e 7e 0a 5c 70 69 63 32 | 33 7b 5c 70 30 33 5c 66 |~~.\pic2|3{\p03\f|
|00003ec0| 20 5c 70 32 33 5c 62 20 | 5c 70 31 32 5c 62 5c 66 | \p23\b |\p12\b\f|
|00003ed0| 20 5c 70 30 31 5c 66 20 | 5c 70 32 31 5c 62 20 5c | \p01\f |\p21\b \|
|00003ee0| 70 31 30 7d 5c 5c 0a 24 | 24 0a 24 41 5c 63 69 72 |p10}\\.$|$.$A\cir|
|00003ef0| 63 20 42 24 20 63 61 6e | 20 62 65 20 64 65 73 63 |c B$ can| be desc|
|00003f00| 72 69 62 65 64 20 61 73 | 20 74 68 65 20 73 75 62 |ribed as| the sub|
|00003f10| 73 74 69 74 75 74 69 6f | 6e 20 6f 66 20 61 20 63 |stitutio|n of a c|
|00003f20| 6f 70 79 20 6f 66 20 24 | 42 24 20 66 6f 72 0a 65 |opy of $|B$ for.e|
|00003f30| 61 63 68 20 65 6c 65 6d | 65 6e 74 20 6f 66 20 24 |ach elem|ent of $|
|00003f40| 41 24 2e 20 20 55 6e 6c | 69 6b 65 20 6f 72 64 69 |A$.  Unl|ike ordi|
|00003f50| 6e 61 6c 20 73 75 6d 2c | 20 6f 72 64 69 6e 61 6c |nal sum,| ordinal|
|00003f60| 20 70 72 6f 64 75 63 74 | 20 64 6f 65 73 20 6e 6f | product| does no|
|00003f70| 74 0a 63 6f 6e 74 72 69 | 62 75 74 65 20 61 6e 79 |t.contri|bute any|
|00003f80| 20 73 65 71 75 65 6e 74 | 69 61 6c 69 74 79 20 6f | sequent|iality o|
|00003f90| 66 20 69 74 73 20 6f 77 | 6e 2c 20 62 75 74 20 72 |f its ow|n, but r|
|00003fa0| 61 74 68 65 72 20 73 65 | 72 76 65 73 20 74 6f 20 |ather se|rves to |
|00003fb0| 6e 65 73 74 0a 69 74 65 | 72 61 74 69 6f 6e 73 2e |nest.ite|rations.|
|00003fc0| 20 20 49 66 20 24 41 24 | 20 61 6e 64 20 24 42 24 |  If $A$| and $B$|
|00003fd0| 20 61 72 65 20 70 75 72 | 65 6c 79 20 63 6f 6e 63 | are pur|ely conc|
|00003fe0| 75 72 72 65 6e 74 20 28 | 64 69 73 63 72 65 74 65 |urrent (|discrete|
|00003ff0| 6c 79 20 6f 72 64 65 72 | 65 64 29 0a 74 68 65 6e |ly order|ed).then|
|00004000| 20 24 41 5c 63 69 72 63 | 20 42 3d 41 5c 74 69 6d | $A\circ| B=A\tim|
|00004010| 65 73 20 42 24 2e 20 20 | 49 66 20 74 68 65 79 20 |es B$.  |If they |
|00004020| 61 72 65 20 70 75 72 65 | 6c 79 20 73 65 71 75 65 |are pure|ly seque|
|00004030| 6e 74 69 61 6c 20 28 63 | 68 61 69 6e 73 29 20 74 |ntial (c|hains) t|
|00004040| 68 65 6e 0a 24 41 5c 63 | 69 72 63 20 42 24 20 69 |hen.$A\c|irc B$ i|
|00004050| 74 65 72 61 74 65 73 20 | 24 42 24 20 24 41 24 20 |terates |$B$ $A$ |
|00004060| 74 69 6d 65 73 2e 20 20 | 49 66 20 24 41 24 20 69 |times.  |If $A$ i|
|00004070| 73 20 73 65 71 75 65 6e | 74 69 61 6c 20 77 68 69 |s sequen|tial whi|
|00004080| 6c 65 20 24 42 24 20 68 | 61 73 0a 73 6f 6d 65 20 |le $B$ h|as.some |
|00004090| 63 6f 6e 63 75 72 72 65 | 6e 63 79 2c 20 74 68 61 |concurre|ncy, tha|
|000040a0| 74 20 63 6f 6e 63 75 72 | 72 65 6e 63 79 20 69 73 |t concur|rency is|
|000040b0| 20 63 6f 6e 66 69 6e 65 | 64 20 74 6f 20 6f 6e 65 | confine|d to one|
|000040c0| 20 69 74 65 72 61 74 69 | 6f 6e 20 6f 66 20 74 68 | iterati|on of th|
|000040d0| 65 0a 69 6e 6e 65 72 20 | 6c 6f 6f 70 2e 20 20 48 |e.inner |loop.  H|
|000040e0| 6f 77 65 76 65 72 20 69 | 66 20 24 42 24 20 69 73 |owever i|f $B$ is|
|000040f0| 20 73 65 71 75 65 6e 74 | 69 61 6c 20 61 6e 64 20 | sequent|ial and |
|00004100| 24 41 24 20 68 61 73 20 | 73 6f 6d 65 20 63 6f 6e |$A$ has |some con|
|00004110| 63 75 72 72 65 6e 63 79 | 0a 74 68 65 6e 20 74 68 |currency|.then th|
|00004120| 65 20 63 6f 72 72 65 73 | 70 6f 6e 64 69 6e 67 20 |e corres|ponding |
|00004130| 63 6f 70 69 65 73 20 6f | 66 20 74 68 65 20 69 6e |copies o|f the in|
|00004140| 6e 65 72 20 6c 6f 6f 70 | 20 61 72 65 20 72 75 6e |ner loop| are run|
|00004150| 20 63 6f 6e 63 75 72 72 | 65 6e 74 6c 79 2e 0a 0a | concurr|ently...|
|00004160| 4f 72 64 69 6e 61 6c 20 | 70 72 6f 64 75 63 74 20 |Ordinal |product |
|00004170| 69 73 20 61 73 73 6f 63 | 69 61 74 69 76 65 20 62 |is assoc|iative b|
|00004180| 75 74 20 6e 6f 74 20 63 | 6f 6d 6d 75 74 61 74 69 |ut not c|ommutati|
|00004190| 76 65 2c 20 61 6e 64 20 | 68 61 73 20 74 68 65 20 |ve, and |has the |
|000041a0| 73 61 6d 65 0a 69 64 65 | 6e 74 69 74 79 20 61 73 |same.ide|ntity as|
|000041b0| 20 63 61 72 64 69 6e 61 | 6c 20 70 72 6f 64 75 63 | cardina|l produc|
|000041c0| 74 2c 20 6e 61 6d 65 6c | 79 20 74 68 65 20 73 69 |t, namel|y the si|
|000041d0| 6e 67 6c 65 74 6f 6e 2e | 20 20 49 74 20 64 69 73 |ngleton.|  It dis|
|000041e0| 74 72 69 62 75 74 65 73 | 0a 6f 76 65 72 20 62 6f |tributes|.over bo|
|000041f0| 74 68 20 63 61 72 64 69 | 6e 61 6c 20 61 6e 64 20 |th cardi|nal and |
|00004200| 6f 72 64 69 6e 61 6c 20 | 73 75 6d 2c 20 62 75 74 |ordinal |sum, but|
|00004210| 20 6f 6e 6c 79 20 6f 6e | 20 74 68 65 20 6c 65 66 | only on| the lef|
|00004220| 74 20 69 6e 20 65 61 63 | 68 20 63 61 73 65 3a 0a |t in eac|h case:.|
|00004230| 24 28 41 2b 42 29 5c 63 | 69 72 63 20 43 3d 41 5c |$(A+B)\c|irc C=A\|
|00004240| 63 69 72 63 20 43 2b 42 | 5c 63 69 72 63 20 43 24 |circ C+B|\circ C$|
|00004250| 20 61 6e 64 20 24 28 41 | 3b 42 29 5c 63 69 72 63 | and $(A|;B)\circ|
|00004260| 20 43 3d 41 5c 63 69 72 | 63 20 43 3b 42 5c 63 69 | C=A\cir|c C;B\ci|
|00004270| 72 63 20 43 24 2e 0a 0a | 54 68 65 20 6f 72 64 69 |rc C$...|The ordi|
|00004280| 6e 61 6c 20 65 78 70 6f | 6e 65 6e 74 69 61 74 69 |nal expo|nentiati|
|00004290| 6f 6e 20 24 5e 41 42 24 | 20 69 73 20 74 68 65 20 |on $^AB$| is the |
|000042a0| 73 65 74 20 6f 66 20 61 | 6c 6c 20 66 75 6e 63 74 |set of a|ll funct|
|000042b0| 69 6f 6e 73 20 66 72 6f | 6d 20 24 41 24 0a 74 6f |ions fro|m $A$.to|
|000042c0| 20 24 42 24 2c 20 7b 5c | 69 74 20 70 72 65 7d 6f | $B$, {\|it pre}o|
|000042d0| 72 64 65 72 65 64 5c 66 | 6f 6f 74 6e 6f 74 65 7b |rdered\f|ootnote{|
|000042e0| 41 20 70 72 65 6f 72 64 | 65 72 20 69 73 20 61 20 |A preord|er is a |
|000042f0| 72 65 66 6c 65 78 69 76 | 65 20 74 72 61 6e 73 69 |reflexiv|e transi|
|00004300| 74 69 76 65 0a 62 69 6e | 61 72 79 20 72 65 6c 61 |tive.bin|ary rela|
|00004310| 74 69 6f 6e 2c 20 6c 61 | 63 6b 69 6e 67 20 61 6e |tion, la|cking an|
|00004320| 74 69 73 79 6d 6d 65 74 | 72 79 2c 20 61 20 70 72 |tisymmet|ry, a pr|
|00004330| 6f 70 65 72 74 79 20 74 | 68 61 74 20 6e 65 65 64 |operty t|hat need|
|00004340| 20 6e 6f 74 20 68 6f 6c | 64 0a 77 68 65 6e 20 74 | not hol|d.when t|
|00004350| 68 65 20 65 78 70 6f 6e | 65 6e 74 20 24 41 24 20 |he expon|ent $A$ |
|00004360| 69 73 20 69 6e 66 69 6e | 69 74 65 2e 7d 20 73 6f |is infin|ite.} so|
|00004370| 20 74 68 61 74 20 24 66 | 5c 73 71 73 75 62 73 65 | that $f|\sqsubse|
|00004380| 74 65 71 20 67 24 20 6a | 75 73 74 20 77 68 65 6e |teq g$ j|ust when|
|00004390| 0a 66 6f 72 20 61 6c 6c | 20 24 78 5c 69 6e 20 58 |.for all| $x\in X|
|000043a0| 24 2c 20 65 69 74 68 65 | 72 20 24 66 28 78 29 5c |$, eithe|r $f(x)\|
|000043b0| 70 72 65 63 65 71 20 67 | 28 78 29 24 20 6f 72 20 |preceq g|(x)$ or |
|000043c0| 24 66 28 78 27 29 5c 70 | 72 65 63 20 67 28 78 27 |$f(x')\p|rec g(x'|
|000043d0| 29 24 20 66 6f 72 0a 73 | 6f 6d 65 20 24 78 27 3e |)$ for.s|ome $x'>|
|000043e0| 78 24 2e 20 20 28 49 6e | 74 75 69 74 69 6f 6e 20 |x$.  (In|tuition |
|000043f0| 73 75 67 67 65 73 74 73 | 20 74 68 69 73 20 73 68 |suggests| this sh|
|00004400| 6f 75 6c 64 20 62 65 20 | 24 78 27 3c 78 24 2c 20 |ould be |$x'<x$, |
|00004410| 62 75 74 20 42 69 72 6b | 68 6f 66 66 0a 6e 6f 74 |but Birk|hoff.not|
|00004420| 69 63 65 64 20 74 68 61 | 74 20 77 68 65 6e 20 24 |iced tha|t when $|
|00004430| 41 24 20 69 73 20 69 6d | 70 6c 69 63 69 74 6c 79 |A$ is im|plicitly|
|00004440| 20 72 65 76 65 72 73 65 | 64 20 69 6e 20 74 68 69 | reverse|d in thi|
|00004450| 73 20 77 61 79 20 74 68 | 65 20 6f 70 65 72 61 74 |s way th|e operat|
|00004460| 69 6f 6e 0a 70 72 65 73 | 65 72 76 65 73 20 63 68 |ion.pres|erves ch|
|00004470| 61 69 6e 73 2e 29 20 20 | 49 6e 20 70 61 72 74 69 |ains.)  |In parti|
|00004480| 63 75 6c 61 72 2c 20 69 | 66 20 61 74 20 24 78 27 |cular, i|f at $x'|
|00004490| 24 20 77 65 20 68 61 76 | 65 20 24 66 28 78 27 29 |$ we hav|e $f(x')|
|000044a0| 5c 70 72 65 63 0a 67 28 | 78 27 29 24 2c 20 74 68 |\prec.g(|x')$, th|
|000044b0| 65 6e 20 69 6e 20 64 65 | 63 69 64 69 6e 67 20 77 |en in de|ciding w|
|000044c0| 68 65 74 68 65 72 20 24 | 66 5c 73 71 73 75 62 73 |hether $|f\sqsubs|
|000044d0| 65 74 65 71 20 67 24 20 | 62 79 20 63 6f 6d 70 61 |eteq g$ |by compa|
|000044e0| 72 69 6e 67 20 24 66 24 | 20 61 6e 64 0a 24 67 24 |ring $f$| and.$g$|
|000044f0| 20 70 6f 69 6e 74 77 69 | 73 65 20 77 65 20 6d 61 | pointwi|se we ma|
|00004500| 79 20 69 67 6e 6f 72 65 | 20 74 68 65 20 72 65 6c |y ignore| the rel|
|00004510| 61 74 69 6f 6e 73 68 69 | 70 20 62 65 74 77 65 65 |ationshi|p betwee|
|00004520| 6e 20 24 66 28 78 29 24 | 20 61 6e 64 20 24 67 28 |n $f(x)$| and $g(|
|00004530| 78 29 24 0a 66 6f 72 20 | 61 6c 6c 20 24 78 3c 78 |x)$.for |all $x<x|
|00004540| 27 24 2e 20 20 46 6f 72 | 20 65 78 61 6d 70 6c 65 |'$.  For| example|
|00004550| 0a 24 24 5e 7b 5c 70 69 | 63 30 31 7b 5c 70 30 31 |.$$^{\pi|c01{\p01|
|00004560| 5c 64 20 20 5c 70 30 30 | 7d 7d 5c 70 69 63 32 31 |\d  \p00|}}\pic21|
|00004570| 7b 5c 70 30 31 5c 66 20 | 5c 70 32 31 5c 62 20 5c |{\p01\f |\p21\b \|
|00004580| 70 31 30 7d 0a 7e 7e 3d | 7e 7e 0a 5c 70 69 63 33 |p10}.~~=|~~.\pic3|
|00004590| 33 7b 5c 70 30 33 5c 66 | 20 5c 70 31 33 5c 64 20 |3{\p03\f| \p13\d |
|000045a0| 5c 70 32 33 5c 64 20 5c | 70 33 33 5c 62 20 5c 70 |\p23\d \|p33\b \p|
|000045b0| 31 32 5c 64 5c 66 20 5c | 70 32 32 5c 62 5c 64 0a |12\d\f \|p22\b\d.|
|000045c0| 5c 70 31 31 20 5c 70 75 | 74 28 31 2c 31 29 7b 5c |\p11 \pu|t(1,1){\|
|000045d0| 6c 69 6e 65 28 20 31 2c | 2d 32 29 7b 2e 35 7d 7d |line( 1,|-2){.5}}|
|000045e0| 0a 5c 70 32 31 20 5c 70 | 75 74 28 32 2c 31 29 7b |.\p21 \p|ut(2,1){|
|000045f0| 5c 6c 69 6e 65 28 2d 31 | 2c 2d 32 29 7b 2e 35 7d |\line(-1|,-2){.5}|
|00004600| 7d 0a 5c 70 75 74 28 31 | 2e 35 2c 30 29 7b 5c 6d |}.\put(1|.5,0){\m|
|00004610| 61 6b 65 62 6f 78 28 30 | 2c 30 29 7b 24 5c 62 75 |akebox(0|,0){$\bu|
|00004620| 6c 6c 65 74 24 7d 7d 7d | 0a 5c 6d 62 6f 78 7b 20 |llet$}}}|.\mbox{ |
|00004630| 20 61 6e 64 20 20 20 20 | 7d 0a 5e 7b 5c 70 69 63 | and    |}.^{\pic|
|00004640| 32 31 7b 5c 70 30 31 5c | 66 20 5c 70 32 31 5c 62 |21{\p01\|f \p21\b|
|00004650| 20 5c 70 31 30 7d 7d 5c | 70 69 63 30 31 7b 5c 70 | \p10}}\|pic01{\p|
|00004660| 30 31 5c 64 20 20 5c 70 | 30 30 7d 0a 7e 7e 3d 7e |01\d  \p|00}.~~=~|
|00004670| 7e 0a 5c 70 69 63 31 35 | 7b 5c 70 31 35 5c 64 20 |~.\pic15|{\p15\d |
|00004680| 5c 70 31 34 5c 62 5c 66 | 20 5c 70 30 33 5c 64 20 |\p14\b\f| \p03\d |
|00004690| 5c 70 32 33 5c 64 20 5c | 70 30 32 5c 66 20 5c 70 |\p23\d \|p02\f \p|
|000046a0| 32 32 5c 62 20 5c 70 31 | 31 5c 64 20 5c 70 31 30 |22\b \p1|1\d \p10|
|000046b0| 7d 2e 0a 24 24 0a 42 6f | 74 68 20 6f 66 20 74 68 |}..$$.Bo|th of th|
|000046c0| 65 73 65 20 61 72 65 20 | 65 61 73 69 6c 79 20 63 |ese are |easily c|
|000046d0| 6f 6d 70 75 74 65 64 20 | 75 73 69 6e 67 20 42 69 |omputed |using Bi|
|000046e0| 72 6b 68 6f 66 66 27 73 | 20 74 77 6f 20 6c 61 77 |rkhoff's| two law|
|000046f0| 73 0a 24 24 7b 5e 7b 42 | 2b 43 7d 41 7d 3d 7b 5e |s.$${^{B|+C}A}={^|
|00004700| 42 41 7d 5c 74 69 6d 65 | 73 7b 5e 43 41 7d 24 24 |BA}\time|s{^CA}$$|
|00004710| 0a 24 24 7b 5e 7b 42 3b | 43 7d 41 7d 3d 7b 5e 43 |.$${^{B;|C}A}={^C|
|00004720| 41 7d 5c 63 69 72 63 7b | 5e 42 41 7d 24 24 0a 54 |A}\circ{|^BA}$$.T|
|00004730| 68 65 20 66 69 72 73 74 | 20 69 73 20 63 6f 6d 70 |he first| is comp|
|00004740| 75 74 65 64 20 61 73 20 | 24 7b 5e 7b 31 3b 31 7d |uted as |${^{1;1}|
|00004750| 41 7d 3d 7b 5e 31 41 7d | 5c 63 69 72 63 7b 5e 31 |A}={^1A}|\circ{^1|
|00004760| 41 7d 3d 41 5c 63 69 72 | 63 20 41 24 20 77 68 65 |A}=A\cir|c A$ whe|
|00004770| 72 65 20 24 41 3d 0a 5c | 70 69 63 32 31 7b 5c 70 |re $A=.\|pic21{\p|
|00004780| 30 31 5c 66 20 5c 70 32 | 31 5c 62 20 5c 70 31 30 |01\f \p2|1\b \p10|
|00004790| 7d 3d 31 3b 28 31 2b 31 | 29 24 2e 20 20 54 68 65 |}=1;(1+1|)$.  The|
|000047a0| 20 73 65 63 6f 6e 64 20 | 69 73 0a 24 7b 5e 7b 31 | second |is.${^{1|
|000047b0| 3b 28 31 2b 31 29 7d 32 | 7d 3d 7b 5e 7b 31 2b 31 |;(1+1)}2|}={^{1+1|
|000047c0| 7d 32 5c 63 69 72 63 7b | 5e 31 32 7d 7d 3d 28 32 |}2\circ{|^12}}=(2|
|000047d0| 5c 74 69 6d 65 73 20 32 | 29 5c 63 69 72 63 32 24 |\times 2|)\circ2$|
|000047e0| 20 77 68 65 72 65 20 24 | 32 3d 31 3b 31 24 0a 28 | where $|2=1;1$.(|
|000047f0| 6f 72 64 69 6e 61 6c 20 | 32 29 2e 0a 0a 41 73 20 |ordinal |2)...As |
|00004800| 61 20 70 72 6f 67 72 61 | 6d 6d 69 6e 67 20 63 6f |a progra|mming co|
|00004810| 6e 6e 65 63 74 69 76 65 | 20 6f 72 64 69 6e 61 6c |nnective| ordinal|
|00004820| 20 65 78 70 6f 6e 65 6e | 74 69 61 74 69 6f 6e 20 | exponen|tiation |
|00004830| 69 6d 70 6c 65 6d 65 6e | 74 73 20 61 0a 67 65 6e |implemen|ts a.gen|
|00004840| 65 72 61 6c 69 7a 65 64 | 20 66 6f 72 6d 20 6f 66 |eralized| form of|
|00004850| 20 60 60 69 74 65 72 61 | 74 65 64 20 69 74 65 72 | ``itera|ted iter|
|00004860| 61 74 69 6f 6e 2e 27 27 | 20 20 57 68 65 6e 20 24 |ation.''|  When $|
|00004870| 41 24 20 69 73 20 61 20 | 63 68 61 69 6e 20 24 5e |A$ is a |chain $^|
|00004880| 41 42 24 0a 69 73 20 74 | 68 65 20 6c 65 78 69 63 |AB$.is t|he lexic|
|00004890| 6f 67 72 61 70 68 69 63 | 20 70 72 6f 64 75 63 74 |ographic| product|
|000048a0| 20 6f 66 20 24 42 24 20 | 77 69 74 68 20 69 74 73 | of $B$ |with its|
|000048b0| 65 6c 66 20 24 7c 41 7c | 24 20 74 69 6d 65 73 3b |elf $|A||$ times;|
|000048c0| 20 74 68 75 73 20 69 66 | 0a 6c 65 78 69 63 6f 67 | thus if|.lexicog|
|000048d0| 72 61 70 68 69 63 20 70 | 72 6f 64 75 63 74 20 69 |raphic p|roduct i|
|000048e0| 73 20 6e 65 73 74 65 64 | 20 69 74 65 72 61 74 69 |s nested| iterati|
|000048f0| 6f 6e 20 74 68 65 6e 20 | 77 65 20 63 61 6e 20 6e |on then |we can n|
|00004900| 6f 77 20 69 74 65 72 61 | 74 65 20 74 68 65 0a 6e |ow itera|te the.n|
|00004910| 65 73 74 69 6e 67 20 70 | 72 6f 63 65 73 73 2e 20 |esting p|rocess. |
|00004920| 20 57 68 65 6e 20 24 41 | 24 20 69 73 20 64 69 73 | When $A|$ is dis|
|00004930| 63 72 65 74 65 20 24 5e | 41 42 24 20 69 73 20 74 |crete $^|AB$ is t|
|00004940| 68 65 20 63 61 72 64 69 | 6e 61 6c 20 70 72 6f 64 |he cardi|nal prod|
|00004950| 75 63 74 20 6f 66 0a 24 | 42 24 20 77 69 74 68 20 |uct of.$|B$ with |
|00004960| 69 74 73 65 6c 66 20 24 | 7c 41 7c 24 20 74 69 6d |itself $||A|$ tim|
|00004970| 65 73 2e 20 20 54 68 65 | 20 61 62 6f 76 65 20 66 |es.  The| above f|
|00004980| 6f 72 6d 75 6c 61 73 20 | 69 6e 64 69 63 61 74 65 |ormulas |indicate|
|00004990| 20 68 6f 77 20 6f 6e 65 | 20 6d 61 79 0a 70 72 6f | how one| may.pro|
|000049a0| 64 75 63 65 20 61 20 6d | 69 78 20 6f 66 20 74 68 |duce a m|ix of th|
|000049b0| 65 73 65 20 70 72 6f 64 | 75 63 74 73 2e 0a 0a 49 |ese prod|ucts...I|
|000049c0| 6e 20 74 68 69 73 20 65 | 78 70 6f 73 69 74 69 6f |n this e|xpositio|
|000049d0| 6e 20 6f 66 20 42 69 72 | 6b 68 6f 66 66 20 61 72 |n of Bir|khoff ar|
|000049e0| 69 74 68 6d 65 74 69 63 | 20 77 65 20 68 61 76 65 |ithmetic| we have|
|000049f0| 20 61 64 68 65 72 65 64 | 20 74 6f 20 42 69 72 6b | adhered| to Birk|
|00004a00| 68 6f 66 66 27 73 0a 75 | 73 65 20 6f 66 20 3d 20 |hoff's.u|se of = |
|00004a10| 69 6e 20 70 6c 61 63 65 | 20 6f 66 20 24 5c 63 6f |in place| of $\co|
|00004a20| 6e 67 24 2e 20 20 54 68 | 69 73 20 73 65 65 6d 69 |ng$.  Th|is seemi|
|00004a30| 6e 67 6c 79 20 68 61 72 | 6d 6c 65 73 73 20 63 6f |ngly har|mless co|
|00004a40| 6e 76 65 6e 74 69 6f 6e | 20 69 73 0a 73 74 72 6f |nvention| is.stro|
|00004a50| 6e 67 6c 79 20 72 65 69 | 6e 66 6f 72 63 65 64 20 |ngly rei|nforced |
|00004a60| 62 79 20 65 78 70 65 72 | 69 65 6e 63 65 20 77 69 |by exper|ience wi|
|00004a70| 74 68 20 74 68 65 20 48 | 61 73 73 65 20 64 69 61 |th the H|asse dia|
|00004a80| 67 72 61 6d 20 72 65 70 | 72 65 73 65 6e 74 61 74 |gram rep|resentat|
|00004a90| 69 6f 6e 0a 6f 66 20 74 | 68 65 20 65 6c 65 6d 65 |ion.of t|he eleme|
|00004aa0| 6e 74 73 20 6f 66 20 70 | 6f 73 65 74 73 20 61 73 |nts of p|osets as|
|00004ab0| 20 61 6e 6f 6e 79 6d 6f | 75 73 20 64 6f 74 73 2e | anonymo|us dots.|
|00004ac0| 0a 0a 4e 65 76 65 72 74 | 68 65 6c 65 73 73 20 74 |..Nevert|heless t|
|00004ad0| 68 69 73 20 63 6f 6e 76 | 65 6e 74 69 6f 6e 20 69 |his conv|ention i|
|00004ae0| 73 20 69 6e 20 63 6f 6e | 66 6c 69 63 74 20 77 69 |s in con|flict wi|
|00004af0| 74 68 20 74 68 65 20 63 | 6f 6e 73 74 72 75 63 74 |th the c|onstruct|
|00004b00| 69 76 65 0a 69 6e 74 65 | 72 70 72 65 74 61 74 69 |ive.inte|rpretati|
|00004b10| 6f 6e 20 6f 66 20 24 41 | 2b 42 5c 63 6f 6e 67 20 |on of $A|+B\cong |
|00004b20| 42 2b 41 24 20 61 73 20 | 69 64 65 6e 74 69 66 79 |B+A$ as |identify|
|00004b30| 69 6e 67 20 61 20 70 61 | 72 74 69 63 75 6c 61 72 |ing a pa|rticular|
|00004b40| 0a 69 73 6f 6d 6f 72 70 | 68 69 73 6d 20 62 65 74 |.isomorp|hism bet|
|00004b50| 77 65 65 6e 20 24 41 2b | 42 24 20 61 6e 64 20 24 |ween $A+|B$ and $|
|00004b60| 42 2b 41 24 20 64 65 74 | 65 72 6d 69 6e 65 64 20 |B+A$ det|ermined |
|00004b70| 62 79 20 74 68 65 20 70 | 72 6f 6f 66 2e 20 20 49 |by the p|roof.  I|
|00004b80| 6e 20 74 68 65 0a 63 61 | 73 65 20 77 68 65 6e 20 |n the.ca|se when |
|00004b90| 24 41 3d 42 3d 31 24 2c | 20 74 68 65 20 73 69 6e |$A=B=1$,| the sin|
|00004ba0| 67 6c 65 74 6f 6e 2c 20 | 74 68 69 73 20 69 73 6f |gleton, |this iso|
|00004bb0| 6d 6f 72 70 68 69 73 6d | 20 66 72 6f 6d 20 24 31 |morphism| from $1|
|00004bc0| 2b 31 24 20 74 6f 20 69 | 74 73 65 6c 66 0a 69 73 |+1$ to i|tself.is|
|00004bd0| 2c 20 6e 6f 74 20 75 6e | 65 78 70 65 63 74 65 64 |, not un|expected|
|00004be0| 6c 79 2c 20 74 68 65 20 | 6f 6e 65 20 74 68 61 74 |ly, the |one that|
|00004bf0| 20 69 6e 74 65 72 63 68 | 61 6e 67 65 73 20 74 68 | interch|anges th|
|00004c00| 65 20 74 77 6f 20 65 6c | 65 6d 65 6e 74 73 20 6f |e two el|ements o|
|00004c10| 66 20 74 68 65 0a 63 61 | 72 64 69 6e 61 6c 20 24 |f the.ca|rdinal $|
|00004c20| 31 2b 31 24 2e 20 20 49 | 6e 20 74 68 69 73 20 63 |1+1$.  I|n this c|
|00004c30| 6f 6e 73 74 72 75 63 74 | 69 76 65 20 69 6e 74 65 |onstruct|ive inte|
|00004c40| 72 70 72 65 74 61 74 69 | 6f 6e 20 24 41 3d 42 24 |rpretati|on $A=B$|
|00004c50| 20 69 73 20 72 65 73 65 | 72 76 65 64 0a 66 6f 72 | is rese|rved.for|
|00004c60| 20 74 68 65 20 7b 5c 69 | 74 20 69 64 65 6e 74 69 | the {\i|t identi|
|00004c70| 74 79 7d 20 69 73 6f 6d | 6f 72 70 68 69 73 6d 20 |ty} isom|orphism |
|00004c80| 6f 6e 20 24 41 24 2c 20 | 6d 61 6b 69 6e 67 20 24 |on $A$, |making $|
|00004c90| 31 2b 31 3d 31 2b 31 24 | 20 61 6e 20 69 6e 73 74 |1+1=1+1$| an inst|
|00004ca0| 61 6e 63 65 0a 6f 66 20 | 24 41 3d 41 24 20 62 75 |ance.of |$A=A$ bu|
|00004cb0| 74 20 6e 6f 74 20 6f 66 | 20 24 41 2b 42 5c 63 6f |t not of| $A+B\co|
|00004cc0| 6e 67 20 42 2b 41 24 2e | 0a 0a 5c 73 65 63 74 69 |ng B+A$.|..\secti|
|00004cd0| 6f 6e 7b 4c 6f 67 69 63 | 20 6f 66 20 53 63 68 65 |on{Logic| of Sche|
|00004ce0| 64 75 6c 65 73 20 61 6e | 64 20 41 75 74 6f 6d 61 |dules an|d Automa|
|00004cf0| 74 61 7d 0a 0a 5c 73 75 | 62 73 65 63 74 69 6f 6e |ta}..\su|bsection|
|00004d00| 7b 4d 6f 74 69 76 61 74 | 69 6f 6e 7d 0a 0a 50 6f |{Motivat|ion}..Po|
|00004d10| 73 65 74 73 20 61 73 20 | 77 65 20 68 61 76 65 20 |sets as |we have |
|00004d20| 75 6e 64 65 72 73 74 6f | 6f 64 20 74 68 65 6d 20 |understo|od them |
|00004d30| 61 62 6f 76 65 20 61 72 | 65 20 69 6e 68 65 72 65 |above ar|e inhere|
|00004d40| 6e 74 6c 79 20 64 65 74 | 65 72 6d 69 6e 69 73 74 |ntly det|erminist|
|00004d50| 69 63 3a 0a 74 68 65 72 | 65 20 69 73 20 6e 6f 20 |ic:.ther|e is no |
|00004d60| 66 72 65 65 20 63 68 6f | 69 63 65 2c 20 69 6e 64 |free cho|ice, ind|
|00004d70| 65 65 64 20 74 68 65 72 | 65 20 69 73 20 6e 6f 20 |eed ther|e is no |
|00004d80| 63 68 6f 69 63 65 20 61 | 74 20 61 6c 6c 2e 20 20 |choice a|t all.  |
|00004d90| 54 68 65 69 72 0a 65 6c | 65 6d 65 6e 74 73 20 61 |Their.el|ements a|
|00004da0| 73 20 65 76 65 6e 74 73 | 20 6d 75 73 74 20 61 6c |s events| must al|
|00004db0| 6c 20 6f 63 63 75 72 2c | 20 63 6f 6e 73 74 72 61 |l occur,| constra|
|00004dc0| 69 6e 65 64 20 6f 6e 6c | 79 20 69 6e 20 74 68 65 |ined onl|y in the|
|00004dd0| 69 72 20 6f 72 64 65 72 | 20 6f 66 0a 6f 63 63 75 |ir order| of.occu|
|00004de0| 72 72 65 6e 63 65 2e 20 | 20 41 64 64 69 6e 67 20 |rrence. | Adding |
|00004df0| 70 6f 73 65 74 20 61 72 | 69 74 68 6d 65 74 69 63 |poset ar|ithmetic|
|00004e00| 20 74 6f 20 74 68 65 20 | 74 68 65 6f 72 79 20 64 | to the |theory d|
|00004e10| 6f 65 73 20 6e 6f 74 20 | 63 68 61 6e 67 65 0a 74 |oes not |change.t|
|00004e20| 68 69 73 3a 20 69 74 73 | 20 6f 70 65 72 61 74 69 |his: its| operati|
|00004e30| 6f 6e 73 20 61 63 74 20 | 6f 6e 20 61 6e 64 20 79 |ons act |on and y|
|00004e40| 69 65 6c 64 20 64 65 74 | 65 72 6d 69 6e 69 73 74 |ield det|erminist|
|00004e50| 69 63 20 62 65 68 61 76 | 69 6f 72 73 2e 0a 0a 57 |ic behav|iors...W|
|00004e60| 68 65 6e 20 73 65 72 69 | 61 6c 69 7a 61 74 69 6f |hen seri|alizatio|
|00004e70| 6e 20 6f 66 20 61 6e 79 | 20 6b 69 6e 64 20 69 73 |n of any| kind is|
|00004e80| 20 62 72 6f 75 67 68 74 | 20 69 6e 74 6f 20 70 6c | brought| into pl|
|00004e90| 61 79 2c 20 6e 6f 6e 64 | 65 74 65 72 6d 69 6e 69 |ay, nond|etermini|
|00004ea0| 73 6d 0a 65 6e 74 65 72 | 73 20 73 6f 20 61 73 20 |sm.enter|s so as |
|00004eb0| 74 6f 20 63 68 6f 6f 73 | 65 20 61 6e 20 6f 72 64 |to choos|e an ord|
|00004ec0| 65 72 20 6f 66 20 73 65 | 72 69 61 6c 69 7a 61 74 |er of se|rializat|
|00004ed0| 69 6f 6e 2e 20 20 46 6f | 72 20 65 76 65 6e 74 73 |ion.  Fo|r events|
|00004ee0| 20 74 68 61 74 20 61 72 | 65 0a 75 6e 72 65 6c 61 | that ar|e.unrela|
|00004ef0| 74 65 64 2c 20 65 2e 67 | 2e 20 66 6f 72 20 72 65 |ted, e.g|. for re|
|00004f00| 61 73 6f 6e 73 20 6f 66 | 20 64 69 73 74 61 6e 63 |asons of| distanc|
|00004f10| 65 2c 20 73 75 63 68 20 | 6e 6f 6e 64 65 74 65 72 |e, such |nondeter|
|00004f20| 6d 69 6e 69 73 6d 20 69 | 73 0a 69 6e 65 73 73 65 |minism i|s.inesse|
|00004f30| 6e 74 69 61 6c 2e 20 20 | 41 20 72 65 6c 61 74 69 |ntial.  |A relati|
|00004f40| 6f 6e 73 68 69 70 20 62 | 65 74 77 65 65 6e 20 74 |onship b|etween t|
|00004f50| 68 65 20 65 76 65 6e 74 | 73 2c 20 65 2e 67 2e 20 |he event|s, e.g. |
|00004f60| 62 6f 74 68 20 75 73 65 | 20 74 68 65 20 73 61 6d |both use| the sam|
|00004f70| 65 0a 75 6e 73 68 61 72 | 61 62 6c 65 20 72 65 73 |e.unshar|able res|
|00004f80| 6f 75 72 63 65 2c 20 6d | 61 79 20 6f 72 20 6d 61 |ource, m|ay or ma|
|00004f90| 79 20 6e 6f 74 20 6d 61 | 6b 65 20 74 68 69 73 20 |y not ma|ke this |
|00004fa0| 6e 6f 6e 64 65 74 65 72 | 6d 69 6e 69 73 6d 20 65 |nondeter|minism e|
|00004fb0| 73 73 65 6e 74 69 61 6c | 2c 0a 62 75 74 20 74 68 |ssential|,.but th|
|00004fc0| 69 73 20 69 73 20 61 20 | 64 69 73 74 69 6e 63 74 |is is a |distinct|
|00004fd0| 69 6f 6e 20 77 65 20 61 | 72 65 20 75 6e 61 62 6c |ion we a|re unabl|
|00004fe0| 65 20 74 6f 20 72 65 70 | 72 65 73 65 6e 74 20 77 |e to rep|resent w|
|00004ff0| 69 74 68 20 70 6c 61 69 | 6e 0a 70 6f 73 65 74 73 |ith plai|n.posets|
|00005000| 2e 20 20 49 6e 20 61 6e | 79 20 63 61 73 65 20 77 |.  In an|y case w|
|00005010| 65 20 6d 61 79 20 71 75 | 69 74 65 20 61 70 70 72 |e may qu|ite appr|
|00005020| 6f 70 72 69 61 74 65 6c | 79 20 72 65 66 65 72 20 |opriatel|y refer |
|00005030| 74 6f 20 74 68 69 73 20 | 6b 69 6e 64 20 6f 66 0a |to this |kind of.|
|00005040| 73 65 72 69 61 6c 69 7a | 61 74 69 6f 6e 2d 69 6e |serializ|ation-in|
|00005050| 64 75 63 65 64 20 6e 6f | 6e 64 65 74 65 72 6d 69 |duced no|ndetermi|
|00005060| 6e 69 73 6d 20 61 73 20 | 7b 5c 69 74 20 65 70 68 |nism as |{\it eph|
|00005070| 65 6d 65 72 61 6c 7d 2e | 0a 0a 54 68 69 73 20 73 |emeral}.|..This s|
|00005080| 69 74 75 61 74 69 6f 6e | 20 61 72 69 73 65 73 20 |ituation| arises |
|00005090| 77 69 74 68 20 66 6f 72 | 6d 61 6c 20 6c 61 6e 67 |with for|mal lang|
|000050a0| 75 61 67 65 73 2c 20 77 | 69 74 68 6f 75 74 20 74 |uages, w|ithout t|
|000050b0| 68 65 20 63 6f 6d 70 6c | 69 63 61 74 69 6f 6e 0a |he compl|ication.|
|000050c0| 6f 66 20 65 70 68 65 6d | 65 72 61 6c 20 6e 6f 6e |of ephem|eral non|
|000050d0| 64 65 74 65 72 6d 69 6e | 69 73 6d 2e 20 20 53 74 |determin|ism.  St|
|000050e0| 72 69 6e 67 73 20 61 72 | 65 20 64 65 74 65 72 6d |rings ar|e determ|
|000050f0| 69 6e 69 73 74 69 63 20 | 69 6e 20 74 68 61 74 20 |inistic |in that |
|00005100| 74 68 65 79 0a 72 65 70 | 72 65 73 65 6e 74 20 74 |they.rep|resent t|
|00005110| 68 65 20 73 65 71 75 65 | 6e 74 69 61 6c 20 6f 63 |he seque|ntial oc|
|00005120| 63 75 72 72 65 6e 63 65 | 20 6f 72 20 75 74 74 65 |currence| or utte|
|00005130| 72 61 6e 63 65 20 6f 66 | 20 74 68 65 69 72 20 73 |rance of| their s|
|00005140| 79 6d 62 6f 6c 73 2c 20 | 61 6c 6c 0a 6f 66 20 77 |ymbols, |all.of w|
|00005150| 68 69 63 68 20 6d 75 73 | 74 20 6f 63 63 75 72 20 |hich mus|t occur |
|00005160| 69 6e 20 74 68 65 20 70 | 72 65 73 63 72 69 62 65 |in the p|rescribe|
|00005170| 64 20 6f 72 64 65 72 2e | 0a 0a 46 6f 72 20 66 6f |d order.|..For fo|
|00005180| 72 6d 61 6c 20 6c 61 6e | 67 75 61 67 65 73 20 74 |rmal lan|guages t|
|00005190| 68 65 20 74 72 69 63 6b | 20 66 6f 72 20 69 6e 74 |he trick| for int|
|000051a0| 72 6f 64 75 63 69 6e 67 | 20 65 73 73 65 6e 74 69 |roducing| essenti|
|000051b0| 61 6c 20 6e 6f 6e 64 65 | 74 65 72 6d 69 6e 69 73 |al nonde|terminis|
|000051c0| 6d 0a 69 73 20 74 6f 20 | 64 65 66 69 6e 65 20 61 |m.is to |define a|
|000051d0| 20 6c 61 6e 67 75 61 67 | 65 20 74 6f 20 62 65 20 | languag|e to be |
|000051e0| 61 20 73 65 74 20 6f 66 | 20 73 74 72 69 6e 67 73 |a set of| strings|
|000051f0| 2c 20 66 72 6f 6d 20 77 | 68 69 63 68 20 6f 6e 65 |, from w|hich one|
|00005200| 20 73 65 6c 65 63 74 73 | 0a 6f 6e 65 20 66 6f 72 | selects|.one for|
|00005210| 20 75 74 74 65 72 61 6e | 63 65 2e 20 20 41 6c 6c | utteran|ce.  All|
|00005220| 20 74 68 65 20 6e 6f 6e | 64 65 74 65 72 6d 69 6e | the non|determin|
|00005230| 69 73 6d 20 69 73 20 63 | 6f 6e 63 65 6e 74 72 61 |ism is c|oncentra|
|00005240| 74 65 64 20 69 6e 20 74 | 68 65 20 73 65 74 0a 73 |ted in t|he set.s|
|00005250| 74 72 75 63 74 75 72 65 | 3a 20 61 20 73 69 6e 67 |tructure|: a sing|
|00005260| 6c 65 20 63 68 6f 69 63 | 65 20 6f 66 20 61 20 73 |le choic|e of a s|
|00005270| 74 72 69 6e 67 20 69 73 | 20 6d 61 64 65 20 66 72 |tring is| made fr|
|00005280| 6f 6d 20 74 68 65 20 77 | 68 6f 6c 65 20 73 65 74 |om the w|hole set|
|00005290| 2e 0a 0a 54 68 65 20 73 | 61 6d 65 20 63 61 6e 20 |...The s|ame can |
|000052a0| 62 65 20 64 6f 6e 65 20 | 66 6f 72 20 70 6f 73 65 |be done |for pose|
|000052b0| 74 73 2c 20 62 79 20 66 | 6f 72 6d 69 6e 67 20 73 |ts, by f|orming s|
|000052c0| 65 74 73 20 6f 66 20 74 | 68 65 6d 2e 20 20 54 68 |ets of t|hem.  Th|
|000052d0| 69 73 20 6e 61 74 75 72 | 61 6c 0a 67 65 6e 65 72 |is natur|al.gener|
|000052e0| 61 6c 69 7a 61 74 69 6f | 6e 20 6f 66 20 66 6f 72 |alizatio|n of for|
|000052f0| 6d 61 6c 20 6c 61 6e 67 | 75 61 67 65 73 20 74 6f |mal lang|uages to|
|00005300| 20 70 61 72 74 69 61 6c | 20 73 74 72 69 6e 67 73 | partial| strings|
|00005310| 2c 20 64 65 66 69 6e 65 | 64 20 61 73 0a 70 6f 73 |, define|d as.pos|
|00005320| 65 74 73 20 6c 61 62 65 | 6c 65 64 20 77 69 74 68 |ets labe|led with|
|00005330| 20 73 79 6d 62 6f 6c 73 | 2c 20 77 61 73 20 66 69 | symbols|, was fi|
|00005340| 72 73 74 20 65 78 70 72 | 65 73 73 65 64 20 63 6c |rst expr|essed cl|
|00005350| 65 61 72 6c 79 20 61 6e | 64 20 73 74 75 64 69 65 |early an|d studie|
|00005360| 64 20 62 79 0a 47 72 61 | 62 6f 77 73 6b 69 20 5c |d by.Gra|bowski \|
|00005370| 63 69 74 65 7b 47 72 61 | 7d 3b 20 73 75 62 73 65 |cite{Gra|}; subse|
|00005380| 71 75 65 6e 74 6c 79 20 | 74 68 65 20 70 72 65 73 |quently |the pres|
|00005390| 65 6e 74 20 61 75 74 68 | 6f 72 20 73 68 6f 72 74 |ent auth|or short|
|000053a0| 65 6e 65 64 0a 60 60 70 | 61 72 74 69 61 6c 20 73 |ened.``p|artial s|
|000053b0| 74 72 69 6e 67 27 27 20 | 74 6f 20 60 60 70 6f 6d |tring'' |to ``pom|
|000053c0| 73 65 74 2e 27 27 0a 0a | 54 68 65 20 64 72 61 77 |set.''..|The draw|
|000053d0| 62 61 63 6b 20 6f 66 20 | 74 68 65 20 73 65 74 20 |back of |the set |
|000053e0| 61 70 70 72 6f 61 63 68 | 20 69 73 20 74 68 61 74 |approach| is that|
|000053f0| 20 69 74 20 6d 6f 76 65 | 73 20 74 68 65 20 74 69 | it move|s the ti|
|00005400| 6d 69 6e 67 20 6f 66 20 | 61 6c 6c 0a 63 68 6f 69 |ming of |all.choi|
|00005410| 63 65 73 20 74 6f 20 74 | 68 65 20 62 65 67 69 6e |ces to t|he begin|
|00005420| 6e 69 6e 67 20 6f 66 20 | 74 68 65 20 65 78 65 63 |ning of |the exec|
|00005430| 75 74 69 6f 6e 2e 20 20 | 4d 61 6e 79 20 70 68 65 |ution.  |Many phe|
|00005440| 6e 6f 6d 65 6e 61 2c 20 | 73 75 63 68 20 61 73 0a |nomena, |such as.|
|00005450| 70 61 72 74 69 61 6c 20 | 63 6f 72 72 65 63 74 6e |partial |correctn|
|00005460| 65 73 73 2c 20 64 6f 20 | 6e 6f 74 20 64 65 70 65 |ess, do |not depe|
|00005470| 6e 64 20 6f 6e 20 74 68 | 69 73 20 74 69 6d 69 6e |nd on th|is timin|
|00005480| 67 2e 20 20 42 75 74 20 | 74 68 65 20 76 65 72 79 |g.  But |the very|
|00005490| 20 61 63 74 20 6f 66 0a | 6d 61 6b 69 6e 67 20 61 | act of.|making a|
|000054a0| 20 63 68 6f 69 63 65 20 | 64 6f 65 73 2e 20 20 49 | choice |does.  I|
|000054b0| 6e 20 63 68 6f 6f 73 69 | 6e 67 20 62 65 74 77 65 |n choosi|ng betwe|
|000054c0| 65 6e 20 74 68 65 20 73 | 74 72 69 6e 67 73 20 24 |en the s|trings $|
|000054d0| 61 62 24 20 61 6e 64 20 | 24 61 63 24 20 77 65 0a |ab$ and |$ac$ we.|
|000054e0| 68 61 76 65 20 74 68 65 | 20 6f 70 74 69 6f 6e 20 |have the| option |
|000054f0| 6f 66 20 64 65 66 65 72 | 72 69 6e 67 20 74 68 65 |of defer|ring the|
|00005500| 20 63 68 6f 69 63 65 20 | 75 6e 74 69 6c 20 61 66 | choice |until af|
|00005510| 74 65 72 20 74 68 65 20 | 24 61 24 2e 20 20 7b 5c |ter the |$a$.  {\|
|00005520| 69 74 20 54 68 69 73 0a | 6f 70 74 69 6f 6e 20 69 |it This.|option i|
|00005530| 73 20 6e 6f 74 20 72 65 | 70 72 65 73 65 6e 74 61 |s not re|presenta|
|00005540| 62 6c 65 20 77 69 74 68 | 20 75 6e 61 64 6f 72 6e |ble with| unadorn|
|00005550| 65 64 20 73 65 74 73 20 | 6f 66 20 73 74 72 69 6e |ed sets |of strin|
|00005560| 67 73 2e 7d 0a 0a 57 68 | 61 74 20 69 73 20 6e 65 |gs.}..Wh|at is ne|
|00005570| 65 64 65 64 20 69 73 20 | 61 20 72 65 70 72 65 73 |eded is |a repres|
|00005580| 65 6e 74 61 74 69 6f 6e | 20 74 68 61 74 20 70 65 |entation| that pe|
|00005590| 72 6d 69 74 73 20 6e 6f | 6e 64 65 74 65 72 6d 69 |rmits no|ndetermi|
|000055a0| 6e 69 73 6d 20 74 6f 20 | 62 65 0a 73 70 72 65 61 |nism to |be.sprea|
|000055b0| 64 20 74 68 72 6f 75 67 | 68 6f 75 74 20 74 68 65 |d throug|hout the|
|000055c0| 20 73 74 72 69 6e 67 20 | 6f 72 20 63 6f 6d 70 75 | string |or compu|
|000055d0| 74 61 74 69 6f 6e 2e 20 | 20 41 73 20 73 75 63 68 |tation. | As such|
|000055e0| 20 6e 6f 6e 64 65 74 65 | 72 6d 69 6e 69 73 6d 0a | nondete|rminism.|
|000055f0| 63 61 6e 20 62 65 20 6c | 6f 63 61 6c 69 7a 65 64 |can be l|ocalized|
|00005600| 20 61 73 20 69 6e 20 74 | 68 65 20 72 65 67 75 6c | as in t|he regul|
|00005610| 61 72 20 65 78 70 72 65 | 73 73 69 6f 6e 20 24 61 |ar expre|ssion $a|
|00005620| 62 63 28 64 2b 65 29 66 | 67 68 24 20 6f 72 0a 77 |bc(d+e)f|gh$ or.w|
|00005630| 69 64 65 73 70 72 65 61 | 64 20 61 73 20 69 6e 20 |idesprea|d as in |
|00005640| 24 61 62 63 64 2b 65 66 | 67 68 24 2c 20 61 20 64 |$abcd+ef|gh$, a d|
|00005650| 69 73 74 69 6e 63 74 69 | 6f 6e 20 74 68 61 74 20 |istincti|on that |
|00005660| 64 69 73 61 70 70 65 72 | 73 20 77 68 65 6e 20 77 |disapper|s when w|
|00005670| 65 0a 69 64 65 6e 74 69 | 66 79 20 24 61 62 63 28 |e.identi|fy $abc(|
|00005680| 64 2b 65 29 66 67 68 24 | 20 77 69 74 68 20 24 61 |d+e)fgh$| with $a|
|00005690| 62 63 64 66 67 68 2b 61 | 62 63 65 66 67 68 24 2e |bcdfgh+a|bcefgh$.|
|000056a0| 0a 0a 4e 6f 6e 64 65 74 | 65 72 6d 69 6e 69 73 6d |..Nondet|erminism|
|000056b0| 20 74 68 65 6e 20 74 61 | 6b 65 73 20 6f 6e 20 6d | then ta|kes on m|
|000056c0| 6f 72 65 20 6f 66 20 74 | 68 65 20 71 75 61 6c 69 |ore of t|he quali|
|000056d0| 74 69 65 73 20 6f 66 20 | 63 6f 6e 63 75 72 72 65 |ties of |concurre|
|000056e0| 6e 63 79 2c 0a 77 68 69 | 63 68 20 74 6f 6f 20 63 |ncy,.whi|ch too c|
|000056f0| 61 6e 20 62 65 20 6c 6f | 63 61 6c 69 7a 65 64 20 |an be lo|calized |
|00005700| 6f 72 20 77 69 64 65 73 | 70 72 65 61 64 2c 20 75 |or wides|pread, u|
|00005710| 73 69 6e 67 20 74 68 65 | 20 73 61 6d 65 20 74 77 |sing the| same tw|
|00005720| 6f 20 72 65 67 75 6c 61 | 72 0a 65 78 70 72 65 73 |o regula|r.expres|
|00005730| 73 69 6f 6e 73 20 62 75 | 74 20 77 69 74 68 20 74 |sions bu|t with t|
|00005740| 68 65 69 72 20 70 6f 73 | 65 74 20 61 72 69 74 68 |heir pos|et arith|
|00005750| 6d 65 74 69 63 20 69 6e | 74 65 72 70 72 65 74 61 |metic in|terpreta|
|00005760| 74 69 6f 6e 20 77 68 65 | 72 65 0a 24 61 62 63 28 |tion whe|re.$abc(|
|00005770| 64 2b 65 29 66 67 68 24 | 20 69 73 20 76 65 72 79 |d+e)fgh$| is very|
|00005780| 20 64 69 66 66 65 72 65 | 6e 74 20 66 72 6f 6d 20 | differe|nt from |
|00005790| 24 61 62 63 64 66 67 68 | 2b 61 62 63 65 66 67 68 |$abcdfgh|+abcefgh|
|000057a0| 24 2e 0a 0a 54 68 69 73 | 20 73 65 63 74 69 6f 6e |$...This| section|
|000057b0| 20 64 65 76 65 6c 6f 70 | 73 20 61 6e 20 65 76 65 | develop|s an eve|
|000057c0| 6e 20 65 61 72 6c 69 65 | 72 20 63 6f 6e 74 72 69 |n earlie|r contri|
|000057d0| 62 75 74 69 6f 6e 20 6f | 66 20 42 69 72 6b 68 6f |bution o|f Birkho|
|000057e0| 66 66 27 73 20 74 68 61 | 6e 0a 70 6f 73 65 74 20 |ff's tha|n.poset |
|000057f0| 61 72 69 74 68 6d 65 74 | 69 63 2c 20 6e 61 6d 65 |arithmet|ic, name|
|00005800| 6c 79 20 74 68 65 20 64 | 75 61 6c 69 74 79 20 6f |ly the d|uality o|
|00005810| 66 20 70 6f 73 65 74 73 | 20 61 6e 64 20 64 69 73 |f posets| and dis|
|00005820| 74 72 69 62 75 74 69 76 | 65 0a 6c 61 74 74 69 63 |tributiv|e.lattic|
|00005830| 65 73 2e 20 20 57 65 20 | 77 69 6c 6c 20 63 6f 6e |es.  We |will con|
|00005840| 73 69 64 65 72 20 76 61 | 72 69 61 74 69 6f 6e 73 |sider va|riations|
|00005850| 20 6f 6e 20 74 68 69 73 | 20 64 75 61 6c 69 74 79 | on this| duality|
|00005860| 20 61 6e 64 20 68 6f 6d | 65 20 69 6e 20 6f 6e 20 | and hom|e in on |
|00005870| 61 0a 76 61 72 69 61 74 | 69 6f 6e 2c 20 65 76 65 |a.variat|ion, eve|
|00005880| 6e 74 20 61 6e 64 20 73 | 74 61 74 65 20 73 70 61 |nt and s|tate spa|
|00005890| 63 65 73 2c 20 61 6e 64 | 20 61 72 67 75 65 20 69 |ces, and| argue i|
|000058a0| 6e 66 6f 72 6d 61 6c 6c | 79 20 74 68 61 74 20 61 |nformall|y that a|
|000058b0| 6d 6f 6e 67 20 61 6c 6c | 0a 74 68 65 73 65 20 76 |mong all|.these v|
|000058c0| 61 72 69 61 74 69 6f 6e | 73 20 74 68 69 73 20 70 |ariation|s this p|
|000058d0| 61 72 74 69 63 75 6c 61 | 72 20 6f 6e 65 20 69 73 |articula|r one is|
|000058e0| 20 6f 70 74 69 6d 61 6c | 20 66 6f 72 20 74 68 65 | optimal| for the|
|000058f0| 20 70 75 72 70 6f 73 65 | 20 6f 66 0a 75 73 69 6e | purpose| of.usin|
|00005900| 67 20 74 68 65 20 64 75 | 61 6c 69 74 79 20 61 73 |g the du|ality as|
|00005910| 20 61 20 6c 6f 67 69 63 | 20 6f 66 20 63 6f 6e 63 | a logic| of conc|
|00005920| 75 72 72 65 6e 63 79 2e | 0a 0a 5c 73 75 62 73 65 |urrency.|..\subse|
|00005930| 63 74 69 6f 6e 7b 4e 61 | 74 75 72 65 20 6f 66 20 |ction{Na|ture of |
|00005940| 42 69 72 6b 68 6f 66 66 | 2d 53 74 6f 6e 65 20 64 |Birkhoff|-Stone d|
|00005950| 75 61 6c 69 74 79 7d 0a | 0a 54 68 65 20 74 68 65 |uality}.|.The the|
|00005960| 6d 65 20 64 65 76 65 6c | 6f 70 65 64 20 68 65 72 |me devel|oped her|
|00005970| 65 20 69 73 20 74 68 61 | 74 20 6f 66 20 73 63 68 |e is tha|t of sch|
|00005980| 65 64 75 6c 65 73 20 24 | 58 24 20 61 6e 64 20 74 |edules $|X$ and t|
|00005990| 68 65 69 72 0a 63 6f 72 | 72 65 73 70 6f 6e 64 69 |heir.cor|respondi|
|000059a0| 6e 67 20 61 75 74 6f 6d | 61 74 61 20 24 41 3d 32 |ng autom|ata $A=2|
|000059b0| 5e 58 24 2e 20 20 54 68 | 65 20 73 74 61 74 65 73 |^X$.  Th|e states|
|000059c0| 20 6f 66 20 74 68 65 20 | 61 75 74 6f 6d 61 74 61 | of the |automata|
|000059d0| 20 61 72 65 20 74 68 65 | 0a 66 75 6e 63 74 69 6f | are the|.functio|
|000059e0| 6e 73 20 66 72 6f 6d 20 | 24 58 24 20 74 6f 20 32 |ns from |$X$ to 2|
|000059f0| 20 28 69 2e 65 2e 20 73 | 75 62 73 65 74 73 20 6f | (i.e. s|ubsets o|
|00005a00| 66 20 24 58 24 29 20 69 | 6e 64 69 63 61 74 69 6e |f $X$) i|ndicatin|
|00005a10| 67 20 66 6f 72 20 65 61 | 63 68 20 65 76 65 6e 74 |g for ea|ch event|
|00005a20| 0a 24 78 5c 69 6e 20 58 | 24 20 77 68 65 74 68 65 |.$x\in X|$ whethe|
|00005a30| 72 20 6f 72 20 6e 6f 74 | 20 69 74 20 68 61 73 20 |r or not| it has |
|00005a40| 62 65 65 6e 20 64 6f 6e | 65 20 79 65 74 2e 0a 0a |been don|e yet...|
|00005a50| 54 68 65 20 73 65 74 73 | 20 24 58 24 20 77 69 74 |The sets| $X$ wit|
|00005a60| 68 20 75 70 20 74 6f 20 | 74 68 72 65 65 20 65 6c |h up to |three el|
|00005a70| 65 6d 65 6e 74 73 20 61 | 72 65 20 61 73 20 66 6f |ements a|re as fo|
|00005a80| 6c 6c 6f 77 73 2e 20 20 | 24 24 5c 65 6d 70 74 79 |llows.  |$$\empty|
|00005a90| 73 65 74 0a 5c 73 70 5c | 70 69 63 30 30 7b 5c 70 |set.\sp\|pic00{\p|
|00005aa0| 30 30 7d 20 5c 73 70 5c | 70 69 63 32 30 7b 5c 70 |00} \sp\|pic20{\p|
|00005ab0| 30 30 20 5c 70 31 30 7d | 20 5c 73 70 5c 70 69 63 |00 \p10}| \sp\pic|
|00005ac0| 32 30 7b 5c 70 30 30 20 | 5c 70 31 30 20 5c 70 32 |20{\p00 |\p10 \p2|
|00005ad0| 30 7d 24 24 20 54 68 65 | 69 72 0a 70 6f 77 65 72 |0}$$ The|ir.power|
|00005ae0| 20 73 65 74 73 20 61 72 | 65 20 74 68 65 20 63 6f | sets ar|e the co|
|00005af0| 72 72 65 73 70 6f 6e 64 | 69 6e 67 20 42 6f 6f 6c |rrespond|ing Bool|
|00005b00| 65 61 6e 20 61 6c 67 65 | 62 72 61 73 2e 20 20 24 |ean alge|bras.  $|
|00005b10| 24 5c 70 69 63 30 30 7b | 5c 70 30 30 7d 0a 5c 73 |$\pic00{|\p00}.\s|
|00005b20| 70 5c 70 69 63 30 31 7b | 5c 70 30 31 5c 64 20 20 |p\pic01{|\p01\d  |
|00005b30| 5c 70 30 30 7d 20 5c 73 | 70 5c 70 69 63 32 32 7b |\p00} \s|p\pic22{|
|00005b40| 5c 70 31 32 5c 62 5c 66 | 20 20 5c 70 30 31 5c 66 |\p12\b\f|  \p01\f|
|00005b50| 20 20 5c 70 32 31 5c 62 | 20 5c 70 31 30 7d 0a 5c |  \p21\b| \p10}.\|
|00005b60| 73 70 5c 70 69 63 32 33 | 7b 5c 70 31 33 5c 62 5c |sp\pic23|{\p13\b\|
|00005b70| 64 5c 66 20 5c 70 30 32 | 5c 64 5c 66 20 5c 70 31 |d\f \p02|\d\f \p1|
|00005b80| 32 5c 62 5c 66 20 20 5c | 70 32 32 5c 62 5c 64 20 |2\b\f  \|p22\b\d |
|00005b90| 5c 70 30 31 5c 66 20 20 | 5c 70 31 31 5c 64 20 20 |\p01\f  |\p11\d  |
|00005ba0| 5c 70 32 31 5c 62 0a 5c | 70 31 30 7d 24 24 20 49 |\p21\b.\|p10}$$ I|
|00005bb0| 74 20 69 73 20 63 6c 65 | 61 72 20 74 68 61 74 20 |t is cle|ar that |
|00005bc0| 74 68 65 72 65 20 69 73 | 20 61 20 31 2d 31 20 63 |there is| a 1-1 c|
|00005bd0| 6f 72 72 65 73 70 6f 6e | 64 65 6e 63 65 20 62 65 |orrespon|dence be|
|00005be0| 74 77 65 65 6e 20 73 65 | 74 73 20 61 6e 64 0a 74 |tween se|ts and.t|
|00005bf0| 68 65 69 72 20 70 6f 77 | 65 72 20 73 65 74 73 2c |heir pow|er sets,|
|00005c00| 20 73 69 6e 63 65 20 74 | 68 65 20 66 6f 72 6d 65 | since t|he forme|
|00005c10| 72 20 63 61 6e 20 62 65 | 20 72 65 63 6f 76 65 72 |r can be| recover|
|00005c20| 65 64 20 61 73 20 74 68 | 65 20 61 74 6f 6d 73 20 |ed as th|e atoms |
|00005c30| 6f 66 20 74 68 65 0a 6c | 61 74 74 65 72 2e 0a 0a |of the.l|atter...|
|00005c40| 4e 6f 77 20 6f 6e 65 20 | 77 6f 75 6c 64 20 6e 61 |Now one |would na|
|00005c50| 74 75 72 61 6c 6c 79 20 | 61 73 73 75 6d 65 20 74 |turally |assume t|
|00005c60| 68 61 74 20 69 66 20 24 | 41 24 20 69 73 20 74 68 |hat if $|A$ is th|
|00005c70| 65 20 61 62 6f 76 65 20 | 65 69 67 68 74 2d 65 6c |e above |eight-el|
|00005c80| 65 6d 65 6e 74 0a 42 6f | 6f 6c 65 61 6e 20 61 6c |ement.Bo|olean al|
|00005c90| 67 65 62 72 61 2c 20 74 | 68 65 6e 20 24 32 5e 41 |gebra, t|hen $2^A|
|00005ca0| 24 20 77 6f 75 6c 64 20 | 62 65 20 61 20 32 35 36 |$ would |be a 256|
|00005cb0| 2d 65 6c 65 6d 65 6e 74 | 20 42 6f 6f 6c 65 61 6e |-element| Boolean|
|00005cc0| 20 61 6c 67 65 62 72 61 | 20 77 69 74 68 0a 38 20 | algebra| with.8 |
|00005cd0| 61 74 6f 6d 73 2e 20 20 | 42 75 74 20 73 75 72 70 |atoms.  |But surp|
|00005ce0| 72 69 73 69 6e 67 6c 79 | 20 24 32 5e 41 24 20 74 |risingly| $2^A$ t|
|00005cf0| 75 72 6e 73 20 6f 75 74 | 20 74 6f 20 62 65 20 69 |urns out| to be i|
|00005d00| 73 6f 6d 6f 72 70 68 69 | 63 20 74 6f 20 74 68 65 |somorphi|c to the|
|00005d10| 0a 33 2d 65 6c 65 6d 65 | 6e 74 20 73 65 74 20 6f |.3-eleme|nt set o|
|00005d20| 66 20 77 68 69 63 68 20 | 24 41 24 20 69 73 20 74 |f which |$A$ is t|
|00005d30| 68 65 20 70 6f 77 65 72 | 20 73 65 74 2e 20 20 54 |he power| set.  T|
|00005d40| 68 65 20 72 65 61 73 6f | 6e 20 66 6f 72 20 74 68 |he reaso|n for th|
|00005d50| 69 73 0a 61 70 70 61 72 | 65 6e 74 20 76 69 6f 6c |is.appar|ent viol|
|00005d60| 61 74 69 6f 6e 20 6f 66 | 20 43 61 6e 74 6f 72 27 |ation of| Cantor'|
|00005d70| 73 20 74 68 65 6f 72 65 | 6d 20 69 73 20 74 68 61 |s theore|m is tha|
|00005d80| 74 20 24 41 24 20 61 6e | 64 20 24 32 24 20 61 72 |t $A$ an|d $2$ ar|
|00005d90| 65 20 6e 6f 74 20 73 65 | 74 73 0a 62 75 74 20 42 |e not se|ts.but B|
|00005da0| 6f 6f 6c 65 61 6e 20 61 | 6c 67 65 62 72 61 73 2c |oolean a|lgebras,|
|00005db0| 20 61 6e 64 20 24 32 5e | 41 24 20 69 73 20 64 65 | and $2^|A$ is de|
|00005dc0| 66 69 6e 65 64 20 74 6f | 20 62 65 20 6e 6f 74 20 |fined to| be not |
|00005dd0| 61 72 62 69 74 72 61 72 | 79 0a 66 75 6e 63 74 69 |arbitrar|y.functi|
|00005de0| 6f 6e 73 20 62 65 74 77 | 65 65 6e 20 74 68 65 20 |ons betw|een the |
|00005df0| 75 6e 64 65 72 6c 79 69 | 6e 67 20 73 65 74 73 20 |underlyi|ng sets |
|00005e00| 6f 66 20 24 41 24 20 61 | 6e 64 20 24 42 24 20 62 |of $A$ a|nd $B$ b|
|00005e10| 75 74 20 72 61 74 68 65 | 72 0a 68 6f 6d 6f 6d 6f |ut rathe|r.homomo|
|00005e20| 72 70 68 69 73 6d 73 2c | 20 74 68 61 74 20 69 73 |rphisms,| that is|
|00005e30| 2c 20 73 74 72 75 63 74 | 75 72 65 2d 70 72 65 73 |, struct|ure-pres|
|00005e40| 65 72 76 69 6e 67 20 66 | 75 6e 63 74 69 6f 6e 73 |erving f|unctions|
|00005e50| 2e 0a 0a 57 65 20 64 69 | 64 20 6e 6f 74 20 6e 6f |...We di|d not no|
|00005e60| 74 69 63 65 20 74 68 69 | 73 20 77 68 65 6e 20 66 |tice thi|s when f|
|00005e70| 6f 72 6d 69 6e 67 20 61 | 75 74 6f 6d 61 74 61 20 |orming a|utomata |
|00005e80| 62 65 63 61 75 73 65 20 | 77 65 20 77 65 72 65 0a |because |we were.|
|00005e90| 65 78 70 6f 6e 65 6e 74 | 69 61 74 69 6e 67 20 70 |exponent|iating p|
|00005ea0| 6c 61 69 6e 20 73 65 74 | 73 2c 20 77 68 6f 73 65 |lain set|s, whose|
|00005eb0| 20 68 6f 6d 6f 6d 6f 72 | 70 68 69 73 6d 73 20 61 | homomor|phisms a|
|00005ec0| 72 65 20 6a 75 73 74 20 | 66 75 6e 63 74 69 6f 6e |re just |function|
|00005ed0| 73 2e 20 20 49 6e 0a 74 | 68 65 20 6f 74 68 65 72 |s.  In.t|he other|
|00005ee0| 20 64 69 72 65 63 74 69 | 6f 6e 20 74 68 65 20 73 | directi|on the s|
|00005ef0| 74 72 75 63 74 75 72 65 | 20 74 6f 20 62 65 20 70 |tructure| to be p|
|00005f00| 72 65 73 65 72 76 65 64 | 20 63 6f 6e 73 69 73 74 |reserved| consist|
|00005f10| 73 20 6f 66 20 7b 5c 69 | 74 20 61 6c 6c 7d 0a 74 |s of {\i|t all}.t|
|00005f20| 68 65 20 6d 65 65 74 73 | 20 61 6e 64 20 6a 6f 69 |he meets| and joi|
|00005f30| 6e 73 20 28 77 65 20 66 | 6f 6c 6c 6f 77 20 44 61 |ns (we f|ollow Da|
|00005f40| 76 65 79 20 61 6e 64 20 | 50 72 69 65 73 74 6c 65 |vey and |Priestle|
|00005f50| 79 20 5c 63 69 74 65 7b | 44 50 7d 20 69 6e 20 75 |y \cite{|DP} in u|
|00005f60| 73 69 6e 67 0a 6d 65 65 | 74 20 61 6e 64 20 6a 6f |sing.mee|t and jo|
|00005f70| 69 6e 20 73 79 6e 6f 6e | 79 6d 6f 75 73 6c 79 20 |in synon|ymously |
|00005f80| 77 69 74 68 20 69 6e 66 | 20 61 6e 64 20 73 75 70 |with inf| and sup|
|00005f90| 29 20 6f 66 20 61 20 63 | 6f 6d 70 6c 65 74 65 20 |) of a c|omplete |
|00005fa0| 42 6f 6f 6c 65 61 6e 0a | 61 6c 67 65 62 72 61 2e |Boolean.|algebra.|
|00005fb0| 20 20 46 6f 72 20 6f 75 | 72 20 65 69 67 68 74 2d |  For ou|r eight-|
|00005fc0| 65 6c 65 6d 65 6e 74 20 | 42 6f 6f 6c 65 61 6e 20 |element |Boolean |
|00005fd0| 61 6c 67 65 62 72 61 20 | 74 68 65 72 65 20 61 72 |algebra |there ar|
|00005fe0| 65 20 6a 75 73 74 20 74 | 68 72 65 65 0a 73 75 63 |e just t|hree.suc|
|00005ff0| 68 20 6d 61 70 73 2c 20 | 6e 61 6d 65 6c 79 20 74 |h maps, |namely t|
|00006000| 68 6f 73 65 20 74 61 6b | 69 6e 67 20 74 77 6f 20 |hose tak|ing two |
|00006010| 6f 66 20 74 68 65 20 61 | 74 6f 6d 73 20 74 6f 20 |of the a|toms to |
|00006020| 30 20 28 74 68 65 20 6c | 6f 77 65 72 20 65 6c 65 |0 (the l|ower ele|
|00006030| 6d 65 6e 74 0a 6f 66 20 | 24 32 24 29 20 61 6e 64 |ment.of |$2$) and|
|00006040| 20 74 68 65 20 74 68 69 | 72 64 20 74 6f 20 31 2e | the thi|rd to 1.|
|00006050| 20 20 4e 6f 20 74 77 6f | 20 6f 66 20 74 68 65 73 |  No two| of thes|
|00006060| 65 20 74 68 72 65 65 20 | 6d 61 70 73 20 61 72 65 |e three |maps are|
|00006070| 20 63 6f 6d 70 61 72 61 | 62 6c 65 0a 70 6f 69 6e | compara|ble.poin|
|00006080| 74 77 69 73 65 2c 20 68 | 65 6e 63 65 20 63 6f 6c |twise, h|ence col|
|00006090| 6c 65 63 74 69 76 65 6c | 79 20 74 68 65 79 20 66 |lectivel|y they f|
|000060a0| 6f 72 6d 20 61 20 64 69 | 73 63 72 65 74 65 20 6f |orm a di|screte o|
|000060b0| 72 20 75 6e 6f 72 64 65 | 72 65 64 20 73 65 74 2e |r unorde|red set.|
|000060c0| 0a 0a 57 65 20 6e 6f 77 | 20 65 78 74 65 6e 64 20 |..We now| extend |
|000060d0| 74 68 69 73 20 64 75 61 | 6c 69 74 79 20 6f 66 66 |this dua|lity off|
|000060e0| 20 69 6e 20 74 77 6f 20 | 64 69 66 66 65 72 65 6e | in two |differen|
|000060f0| 74 20 64 69 72 65 63 74 | 69 6f 6e 73 2c 20 77 65 |t direct|ions, we|
|00006100| 62 73 20 61 6e 64 0a 70 | 6f 73 65 74 73 2c 20 61 |bs and.p|osets, a|
|00006110| 6e 64 20 74 68 65 6e 20 | 72 65 75 6e 69 74 65 20 |nd then |reunite |
|00006120| 74 68 65 6d 20 61 73 20 | 65 76 65 6e 74 20 73 74 |them as |event st|
|00006130| 72 75 63 74 75 72 65 73 | 2e 0a 0a 41 20 7b 5c 69 |ructures|...A {\i|
|00006140| 74 20 77 65 62 7d 20 5c | 63 69 74 65 7b 47 69 72 |t web} \|cite{Gir|
|00006150| 38 37 7d 20 69 73 20 61 | 6e 20 75 6e 64 69 72 65 |87} is a|n undire|
|00006160| 63 74 65 64 20 67 72 61 | 70 68 20 77 69 74 68 6f |cted gra|ph witho|
|00006170| 75 74 20 73 65 6c 66 2d | 6c 6f 6f 70 73 2c 0a 65 |ut self-|loops,.e|
|00006180| 71 75 69 76 61 6c 65 6e | 74 6c 79 20 61 6e 20 69 |quivalen|tly an i|
|00006190| 72 72 65 66 6c 65 78 69 | 76 65 20 73 79 6d 6d 65 |rreflexi|ve symme|
|000061a0| 74 72 69 63 20 62 69 6e | 61 72 79 20 72 65 6c 61 |tric bin|ary rela|
|000061b0| 74 69 6f 6e 2e 20 20 57 | 65 20 74 68 69 6e 6b 20 |tion.  W|e think |
|000061c0| 6f 66 20 74 68 65 0a 65 | 64 67 65 73 20 61 73 20 |of the.e|dges as |
|000061d0| 65 78 70 72 65 73 73 69 | 6e 67 20 61 20 63 6f 6e |expressi|ng a con|
|000061e0| 66 6c 69 63 74 5c 66 6f | 6f 74 6e 6f 74 65 7b 47 |flict\fo|otnote{G|
|000061f0| 69 72 61 72 64 20 61 73 | 73 69 67 6e 73 20 74 68 |irard as|signs th|
|00006200| 65 20 6f 70 70 6f 73 69 | 74 65 20 6f 72 0a 64 75 |e opposi|te or.du|
|00006210| 61 6c 20 69 6e 74 65 72 | 70 72 65 74 61 74 69 6f |al inter|pretatio|
|00006220| 6e 3a 20 65 64 67 65 73 | 20 64 65 6e 6f 74 65 20 |n: edges| denote |
|00006230| 63 6f 6d 70 61 74 69 62 | 69 6c 69 74 79 20 6f 72 |compatib|ility or|
|00006240| 20 7b 5c 69 74 20 63 6f | 68 65 72 65 6e 63 65 7d | {\it co|herence}|
|00006250| 2e 20 20 42 79 0a 63 68 | 6f 6f 73 69 6e 67 20 74 |.  By.ch|oosing t|
|00006260| 6f 20 73 68 6f 77 20 74 | 68 65 20 63 6f 6e 66 6c |o show t|he confl|
|00006270| 69 63 74 73 20 69 6e 73 | 74 65 61 64 20 77 65 20 |icts ins|tead we |
|00006280| 64 6f 6e 27 74 20 68 61 | 76 65 20 74 6f 20 67 6f |don't ha|ve to go|
|00006290| 20 62 61 63 6b 20 61 6e | 64 0a 72 65 64 72 61 77 | back an|d.redraw|
|000062a0| 20 74 68 65 20 66 6f 75 | 72 20 63 6f 6e 66 6c 69 | the fou|r confli|
|000062b0| 63 74 2d 66 72 65 65 20 | 73 65 74 73 20 77 65 20 |ct-free |sets we |
|000062c0| 73 74 61 72 74 65 64 20 | 77 69 74 68 2e 7d 20 62 |started |with.} b|
|000062d0| 65 74 77 65 65 6e 20 69 | 74 73 0a 65 6e 64 70 6f |etween i|ts.endpo|
|000062e0| 69 6e 74 73 2e 20 20 4f | 66 20 74 68 65 20 77 65 |ints.  O|f the we|
|000062f0| 62 73 20 77 69 74 68 20 | 61 74 20 6d 6f 73 74 20 |bs with |at most |
|00006300| 74 68 72 65 65 20 65 6c | 65 6d 65 6e 74 73 2c 20 |three el|ements, |
|00006310| 74 68 65 20 66 6f 75 72 | 20 64 69 73 63 72 65 74 |the four| discret|
|00006320| 65 0a 6f 72 20 63 6f 6e | 66 6c 69 63 74 2d 66 72 |e.or con|flict-fr|
|00006330| 65 65 20 6f 6e 65 73 20 | 61 70 70 65 61 72 20 61 |ee ones |appear a|
|00006340| 62 6f 76 65 2e 20 20 54 | 68 65 20 72 65 6d 61 69 |bove.  T|he remai|
|00006350| 6e 69 6e 67 20 66 6f 75 | 72 20 61 72 65 20 61 73 |ning fou|r are as|
|00006360| 0a 66 6f 6c 6c 6f 77 73 | 2e 20 20 24 24 5c 70 69 |.follows|.  $$\pi|
|00006370| 63 32 30 7b 5c 70 30 30 | 5c 48 20 5c 70 31 30 7d |c20{\p00|\H \p10}|
|00006380| 20 5c 73 70 5c 70 69 63 | 32 31 7b 5c 70 30 31 5c | \sp\pic|21{\p01\|
|00006390| 48 48 20 5c 70 32 31 20 | 5c 70 31 30 7d 0a 5c 73 |HH \p21 |\p10}.\s|
|000063a0| 70 5c 70 69 63 32 31 7b | 5c 70 30 31 5c 46 20 5c |p\pic21{|\p01\F \|
|000063b0| 70 32 31 5c 42 20 5c 70 | 31 30 7d 20 5c 73 70 5c |p21\B \p|10} \sp\|
|000063c0| 70 69 63 32 31 7b 5c 70 | 30 31 5c 48 48 5c 46 20 |pic21{\p|01\HH\F |
|000063d0| 5c 70 32 31 5c 42 20 5c | 70 31 30 7d 24 24 20 54 |\p21\B \|p10}$$ T|
|000063e0| 68 65 69 72 0a 64 75 61 | 6c 20 61 75 74 6f 6d 61 |heir.dua|l automa|
|000063f0| 74 61 20 72 65 61 6c 69 | 7a 65 20 74 68 65 20 6e |ta reali|ze the n|
+--------+-------------------------+-------------------------+--------+--------+